I recently came across a lovely combinatorial problem in R J Lipton's blog Gödel's lost letter and P=NP. You can read about it in that blog, together with its provenance, and its beautiful solution. However, in order for my comments on it to make any sense I need to recap the problem and its solution.
9 beetles are placed around a circle and the distances between them are the prime numbers 2, 3, 5, 7, 11, 13, 17, 19, 23. They start walking around the circle at the speed of 1 unit of distance per second but their directions are chosen randomly. When two beetles collide they reverse their directions but maintain their same speed. After 50 seconds and many collisions what are the distances between the beetles?
The remarkable answer is that the set of distances is still that same set of prime numbers.
The red herring in the problem is that the presence of prime numbers is irrelevant: no matter what the initial distances are the set of distances returns to that initial set after 50 seconds. The only thing that matters is that the sum of the distances is 100 which is therefore the length of the circle's circumference. The key insight is to imagine that each beetle carries a flag and whenever two beetles collide they exchange flags. Thus each flag continues to travel in the same direction it began with and so, after 50 seconds, it has travelled 50 units of distance and therefore has travelled halfway around the circle to the antipodal point. Since the final position of the flags is a reflection in a centre point mirror of the initial position, the set of distances between the flags is is the same as the original set of distances. However every flag has a beetle on it and therefore this is also true of the set of distances between the beetles.
Of course after 100 secs every flag has returned to its starting position and again the original distances are restored. However it is hardly ever the case that the beetles themselves have returned to their original positions. My friend Dennis McCaughan asked "When do the beetles get back to their original position?" and he and I quickly worked out the answer.
It is obvious that the relative order of the beetles around the circle never changes (as two beetles never swap places). After 100 seconds each beetle has moved to one of the original beetle positions, say through t original clockwise beetle positions, and t is the same for every beetle; t can be positive or negative. The clockwise distance a beetle has travelled is its clockwise drift, a sum of t original consecutive distances. The total clockwise drift is the sum of the individual drifts and in this sum each original distance occurs t times. So the total clockwise drift is 100t.
Initially let there be x beetles moving clockwise and y=9-x beetles moving anticlockwise. Since every collision is between a clockwise beetle and an anticlockwise beetle (turning a clockwise beetle into an anticlockwise one and vice versa) x and y do not change. We can think of d=x-y as the speed of clockwise "drift", the amount of clockwise distance consumed per second. Therefore the total clockwise drift after 100 seconds must be 100d. Hence 100d = 100t and so d = t.
We can now determine when the beetles will all return to their original positions. If d=9 or -9 then, after 100 secs, the beetles will be back in place after 100 seconds since each beetle will have moved through 9 original beetle positions. If d=3 or -3 then after 100 seconds each beetle will have moved through 3 original beetle positions clockwise or anticlockwise. So 300 seconds brings them back to place. For other values of d, a full 900 seconds is required.
Wednesday, 20 May 2020
Sunday, 17 May 2020
A puzzle about disease transmission
I heard this puzzle over 30 years ago when it was circling in North American Computer Science academic circles. The current pandemic and how to stem its spread reminded me of the puzzle. It concerns three sailors, one prostitute and two condoms. Stop reading now if you find that scenario too unsavoury.
The four characters have agreed that each sailor will have intercourse with the prostitute and the problem is to do this safely with only the two condoms at their disposal. What does "safely" mean here? Certainly they wish to guard against the sexual acts resulting in conception but they are all aware that, given the company they have been keeping, one or more of them may have one or more STDs and they don't want any further infection to be transmitted. There is a short discussion of the problem in this Reddit thread.
The solution is not that hard although it is quite easy to find convincing "almost" solutions. Here is one. Sailor Donald wears the first condom and has his wicked way. Then sailor Eric puts on the second condom and then the first condom over it and does the deed. Finally sailor Jared turns the second condom inside out, puts it on, then puts on the first condom over it and completes the action.
This fails in one respect only: Donald has infected the inner surface of the first condom; during the second act this infection is transmitted to the outer surface of the second condom, and so Jared can become infected by Donald's poison. A further incorrect solution appears in the Reddit thread (and then corrected).
The true solution is very similar. Donald uses both condoms (the second inside the first); Eric uses the first condom, Jared turns the second condom inside out and then dons the first condom.
In each sexual act the prostitute is only in contact with the outer surface of the first condom and so she cannot contract a fresh infection. Each man's member touches a condom surface untainted by any infection. All quite easy and possibly a puzzle and solution known to many.
I offer one final twist. Suppose there are 2n+1 sailors and n+1 condoms (but still one prostitute). How about safe sex now?
Let's number the sailors 0 to 2n and the condoms 0 to n.
For each i = 0 to n-1 sailor i wears condom i and also condom 0 over it
Sailor n just uses the single condom 0
For each i = 1 to n sailor n+i wears condom i inside out and also condom 0 over it.
The four characters have agreed that each sailor will have intercourse with the prostitute and the problem is to do this safely with only the two condoms at their disposal. What does "safely" mean here? Certainly they wish to guard against the sexual acts resulting in conception but they are all aware that, given the company they have been keeping, one or more of them may have one or more STDs and they don't want any further infection to be transmitted. There is a short discussion of the problem in this Reddit thread.
The solution is not that hard although it is quite easy to find convincing "almost" solutions. Here is one. Sailor Donald wears the first condom and has his wicked way. Then sailor Eric puts on the second condom and then the first condom over it and does the deed. Finally sailor Jared turns the second condom inside out, puts it on, then puts on the first condom over it and completes the action.
This fails in one respect only: Donald has infected the inner surface of the first condom; during the second act this infection is transmitted to the outer surface of the second condom, and so Jared can become infected by Donald's poison. A further incorrect solution appears in the Reddit thread (and then corrected).
The true solution is very similar. Donald uses both condoms (the second inside the first); Eric uses the first condom, Jared turns the second condom inside out and then dons the first condom.
In each sexual act the prostitute is only in contact with the outer surface of the first condom and so she cannot contract a fresh infection. Each man's member touches a condom surface untainted by any infection. All quite easy and possibly a puzzle and solution known to many.
I offer one final twist. Suppose there are 2n+1 sailors and n+1 condoms (but still one prostitute). How about safe sex now?
Let's number the sailors 0 to 2n and the condoms 0 to n.
For each i = 0 to n-1 sailor i wears condom i and also condom 0 over it
Sailor n just uses the single condom 0
For each i = 1 to n sailor n+i wears condom i inside out and also condom 0 over it.
Monday, 31 December 2018
Widening the franchise
Before the second world war the voting age in most countries was 21 but in the second half of the twentieth century the age of 18 gradually became very common. For example, the USA passed the 26th amendment to its constitution in 1971 largely because it was felt that to be conscripted at age 18 and not allowed to vote was anomalous. There are a few countries where the voting age is 16 (such as Austria) and a very few where it is higher than 18 (such as Kuwait and Bahrain). In many countries there have been movements to bring the age down to 16 (for example, the UK, Australia, and New Zealand) but these attempts were abandoned (although, for the 2014 Scottish Independence referendum, the voting age was 16).
The reason that 18 has emerged as the most common voting age seems to be that 18 is seen as the age when children become adults. That this transition should occur instantly on an eighteenth birthday is obviously a fiction and therefore it is legitimate to ask whether we have got the age right, and to ask whether adulthood is the criterion we should be using.
The assumption that adulthood is a prerequisite to vote is very ingrained. Surely, it is said, a certain maturity is essential before a considered vote can be cast. And yet the right candidate to vote for and the right set of policies to support are generally not decisions that are arrived at by the tools of knowledge and logic; because, if they were, there would be no dispute at the ballot box. Once one accepts that opinions are driven by prejudice and emotion who is to say that a 16 year old is not as qualified as an 18 year old? Let's be honest and admit that most people vote out of self interest even if they are able to rationalise their decisions.
So why should the voting age not be 16? But isn't that as arbitrary as 18? If you are thinking along those lines consider the very bold proposal by Cambridge Professor David Runciman. He suggests the voting age should be lowered to 6! He has admitted that his proposal is made with a certain tongue in cheek but is ready to defend it anyway. For example, what of the objection that children will just vote as their parents tell them? Why should they? Women did not vote the way their husbands said they should when they got the franchise?
For me, the most compelling reason for taking Runciman seriously is that our electorate is already top heavy with old people. The most compelling issues of our age - climate change, whether Scotland should have independence, how should institutionalised racialism be addressed in the USA and other countries - are long term issues. Why should old people have any say in these? Leave it to the citizens who have the most skin in the game. After all if, like me, you are appalled at how the majority of the UK voters voted in the EU referendum, consider what might have happened if the franchise had consisted also of 16 and 17 year olds (a proposal that was seriously floated in 2015). Don't you think their youthful good sense would have prevailed over the grey vote which, on the day, carried the Leave side over the line?
The reason that 18 has emerged as the most common voting age seems to be that 18 is seen as the age when children become adults. That this transition should occur instantly on an eighteenth birthday is obviously a fiction and therefore it is legitimate to ask whether we have got the age right, and to ask whether adulthood is the criterion we should be using.
The assumption that adulthood is a prerequisite to vote is very ingrained. Surely, it is said, a certain maturity is essential before a considered vote can be cast. And yet the right candidate to vote for and the right set of policies to support are generally not decisions that are arrived at by the tools of knowledge and logic; because, if they were, there would be no dispute at the ballot box. Once one accepts that opinions are driven by prejudice and emotion who is to say that a 16 year old is not as qualified as an 18 year old? Let's be honest and admit that most people vote out of self interest even if they are able to rationalise their decisions.
So why should the voting age not be 16? But isn't that as arbitrary as 18? If you are thinking along those lines consider the very bold proposal by Cambridge Professor David Runciman. He suggests the voting age should be lowered to 6! He has admitted that his proposal is made with a certain tongue in cheek but is ready to defend it anyway. For example, what of the objection that children will just vote as their parents tell them? Why should they? Women did not vote the way their husbands said they should when they got the franchise?
For me, the most compelling reason for taking Runciman seriously is that our electorate is already top heavy with old people. The most compelling issues of our age - climate change, whether Scotland should have independence, how should institutionalised racialism be addressed in the USA and other countries - are long term issues. Why should old people have any say in these? Leave it to the citizens who have the most skin in the game. After all if, like me, you are appalled at how the majority of the UK voters voted in the EU referendum, consider what might have happened if the franchise had consisted also of 16 and 17 year olds (a proposal that was seriously floated in 2015). Don't you think their youthful good sense would have prevailed over the grey vote which, on the day, carried the Leave side over the line?
Sunday, 29 April 2018
The trauma of the United States
Recently I read "Loaded" by Roxanne Dunbar-Ortiz. It is a history about the US Constitution's Second Amendment and the mythology surrounding it. The Second Amendment is once again in the news for a reason that occurs with depressing frequency. This time it is the shooting that occurred at the Douglas High School in Florida in February and which has resulted in a mass movement Never Again led by some of the survivors at the school.
I must confess that I began Dunbar-Ortiz's book with pessimism. I expected to read the usual arguments for gun control and the usual counter-arguments and I thought cynically that believing anything would really change was just pie in the sky. That is not exactly how it worked out.
The first thing to say is that the book has a deep and well-researched thesis that the history of the USA from even before its foundation contains a number of deeply disturbing causes for the national gun culture that go way beyond the usual excuses. This is not about personal freedoms endowed to the citizenry by the Founding Fathers. It is not about the national hunting culture. Nor is it about the distrust fostered by the NRA that the government wants to disarm the people to enable their suppression ("from my cold dead hands").
No, it is about slavery and genocide. The US Constitution is not about all men being created equal; it is about the privileges of white male landowners and the second amendment is why white male landowners needed guns. They needed guns to contain their slaves through patrols looking for escapees. And they needed guns to carry out the systemic slaughter of Native Americans so that their lands could be seized. It is interesting to reflect that a key reason for the Declaration of Independence is that King George III tried to restrict the colonists' "right" to seize territory west of the Appalachian mountains whose inhabitants were described as "merciless Indian Savages".
This is not an interpretation of their history that most Americans will like. They are more used to a narrative in which heroic settlers fought for their freedom from an oppressive colonial tyrant and then, through the nineteenth century, expanded ever westwards claiming land for themselves. A history in which brave cowboys and fearless rangers protected farmers from violent attacks by Indians and they came into their manifest destiny much like the Old Testament Jews settling Canaan (just after God gave them their marching orders to kill every one of the original inhabitants). These myths protect them from their murderous pasts and are part of the defence of their wide gun ownership. They revere the part that guns played in taming their land, they laud the bravery of the family man whose gun is to protect his nearest and dearest as part of a long tradition, and they hold their constitution in almost superstitious awe.
So, on reaching the end of the book, I had a sense of hopelessness. How on earth could one penetrate these myths so that a rational discussion about how to go forward could be held? After a few days I began to read some other historical material in the same vein and this left me feeling a little more optimistic. To begin with the USA is not the only country burdened by a very shameful history. The Doctrine of Discovery promulgated by Pope Alexander VI in 1493 initially gave the Spanish permission to take possession of colonise any lands they discovered which were not under the control of a Christian ruler and it became the justification for later European powers to colonise at will (and the American colonists inherited this idea from the British). The world is still suffering from the aftermath of colonisation by force but other colonial powers have at least begun to recognise their catastrophic agency with apologies, reparations, and deliberate reconciliation. The American haven't really started down this road but they did come late to the game - maybe their eyes will be opened in due time.
But also we should not overlook that there are movements in the USA that are trying to confront their racist misogynistic culture: the Woman's Movement, Metoo, the LGBT movement, Black Lives Matter and more. Some of these movements have extraordinary charismatic leaders who recognise the extreme difficulty rank and file Americans have in facing up to their past. I encourage you to view the lecture by Mark Charles; he is a native American who, for all his criticism of the oppression of his people, ends his lecture with some prescriptions that might change the discourse. We have a long way to go (and other colonial powers are still travelling that road) but it is important to try to keep reason, tolerance and understanding alive - and maybe in a couple of hundred years we can emerge in an enlightened sunshine.
I must confess that I began Dunbar-Ortiz's book with pessimism. I expected to read the usual arguments for gun control and the usual counter-arguments and I thought cynically that believing anything would really change was just pie in the sky. That is not exactly how it worked out.
The first thing to say is that the book has a deep and well-researched thesis that the history of the USA from even before its foundation contains a number of deeply disturbing causes for the national gun culture that go way beyond the usual excuses. This is not about personal freedoms endowed to the citizenry by the Founding Fathers. It is not about the national hunting culture. Nor is it about the distrust fostered by the NRA that the government wants to disarm the people to enable their suppression ("from my cold dead hands").
No, it is about slavery and genocide. The US Constitution is not about all men being created equal; it is about the privileges of white male landowners and the second amendment is why white male landowners needed guns. They needed guns to contain their slaves through patrols looking for escapees. And they needed guns to carry out the systemic slaughter of Native Americans so that their lands could be seized. It is interesting to reflect that a key reason for the Declaration of Independence is that King George III tried to restrict the colonists' "right" to seize territory west of the Appalachian mountains whose inhabitants were described as "merciless Indian Savages".
This is not an interpretation of their history that most Americans will like. They are more used to a narrative in which heroic settlers fought for their freedom from an oppressive colonial tyrant and then, through the nineteenth century, expanded ever westwards claiming land for themselves. A history in which brave cowboys and fearless rangers protected farmers from violent attacks by Indians and they came into their manifest destiny much like the Old Testament Jews settling Canaan (just after God gave them their marching orders to kill every one of the original inhabitants). These myths protect them from their murderous pasts and are part of the defence of their wide gun ownership. They revere the part that guns played in taming their land, they laud the bravery of the family man whose gun is to protect his nearest and dearest as part of a long tradition, and they hold their constitution in almost superstitious awe.
So, on reaching the end of the book, I had a sense of hopelessness. How on earth could one penetrate these myths so that a rational discussion about how to go forward could be held? After a few days I began to read some other historical material in the same vein and this left me feeling a little more optimistic. To begin with the USA is not the only country burdened by a very shameful history. The Doctrine of Discovery promulgated by Pope Alexander VI in 1493 initially gave the Spanish permission to take possession of colonise any lands they discovered which were not under the control of a Christian ruler and it became the justification for later European powers to colonise at will (and the American colonists inherited this idea from the British). The world is still suffering from the aftermath of colonisation by force but other colonial powers have at least begun to recognise their catastrophic agency with apologies, reparations, and deliberate reconciliation. The American haven't really started down this road but they did come late to the game - maybe their eyes will be opened in due time.
But also we should not overlook that there are movements in the USA that are trying to confront their racist misogynistic culture: the Woman's Movement, Metoo, the LGBT movement, Black Lives Matter and more. Some of these movements have extraordinary charismatic leaders who recognise the extreme difficulty rank and file Americans have in facing up to their past. I encourage you to view the lecture by Mark Charles; he is a native American who, for all his criticism of the oppression of his people, ends his lecture with some prescriptions that might change the discourse. We have a long way to go (and other colonial powers are still travelling that road) but it is important to try to keep reason, tolerance and understanding alive - and maybe in a couple of hundred years we can emerge in an enlightened sunshine.
Friday, 20 April 2018
A Higher Loyalty
Former FBI Director James Comey published his keenly anticipated book "A Higher Loyalty" this week. I listened to the Audible edition read by Comey himself. This turned out to be a good method of digesting the book because Comey's earnestness comes through very clearly in his own voice.
The book is autobiographical but not a full autobiography. Those who read it just for the events surrounding Donald Trump should not ignore the larger part of the book which deals with episodes from Comey's childhood and career in the law. They are dramatic, thoughtful, and interesting. Comey uses them to develop his views on ethical leadership, self-knowledge and humility describing several people he has known whose lives and personalities have been exemplars for him through the years.
He has much to say about what makes an inspiring leader and it is clear that he wishes he will have been seen as such. Readers will naturally be on their guard for self-serving stories when he talks about the organisations he himself has led but Comey's frequent admissions of his own mistakes and weaknesses lead one to think that we are reading a broadly honest account.
To many people his investigation into Hilary Clinton's unclassified email server will be the black mark forever held against him. These investigations are described in greater detail than anything else in the book. Comey admits that another FBI Director might have handled things somewhat differently but, reading his account, it is difficult not to sympathise with the way he made some incredibly difficult decisions. If (like I had been) you are slightly unclear on what this investigation was about this part of the book is a very complete account. The bottom line is that Clinton was very careless in using an unclassified email server. That conclusion was easily reached but it took the FBI much longer to trawl through the emails before being able to declare that there was nothing further to the whole issue. Comey reported the closure of the investigation to Congress in July 2016. But two weeks before the 2016 election, the investigation had to be re-opened because further emails were found on another laptop and Comey had to decide whether to inform Congress the investigation was being re-opened. He chose to do so and it is this that Clinton and others believe cost the Democrats the election. Should he have waited until the reopened investigation was complete? That might have resulted in Clinton being elected and then the public finding out she was about to be indicted.
I feel there is an unanswered question lurking over this reopening of the investigation: Comey says he had to make this public because the ongoing examination was projected to take weeks yet, in the event, it was completed before the election; had that been known why could the announcement not have been delayed until the investigation was complete?
Donald Trump enters only in the final stages of the book but it is this part of the book that has attracted the most attention. In some ways though, one can read the previous part of the book as setting the scene for Comey's withering criticism of the US President. Comey has constructed a number of ethical principles based on leaders who have influenced his own life and we know, as the moment approaches, that Trump is going to fall very far short of those standards. And, for once, Trump does not disappoint us.
I write this as one who thinks that Donald Trump is a peculiarly awful individual and president. But, of course, some Republicans will not agree. The attacks on Comey have already begun and are being spearheaded by the web site lyincomey.com. I've just spent some time perusing this site and found that its rebuttals are weak and ludicrous. So I think A Higher Loyalty is a very credible attack on the Trump presidency and will only add to the maelstrom of difficulties now swirling around it.
The book is autobiographical but not a full autobiography. Those who read it just for the events surrounding Donald Trump should not ignore the larger part of the book which deals with episodes from Comey's childhood and career in the law. They are dramatic, thoughtful, and interesting. Comey uses them to develop his views on ethical leadership, self-knowledge and humility describing several people he has known whose lives and personalities have been exemplars for him through the years.
He has much to say about what makes an inspiring leader and it is clear that he wishes he will have been seen as such. Readers will naturally be on their guard for self-serving stories when he talks about the organisations he himself has led but Comey's frequent admissions of his own mistakes and weaknesses lead one to think that we are reading a broadly honest account.
To many people his investigation into Hilary Clinton's unclassified email server will be the black mark forever held against him. These investigations are described in greater detail than anything else in the book. Comey admits that another FBI Director might have handled things somewhat differently but, reading his account, it is difficult not to sympathise with the way he made some incredibly difficult decisions. If (like I had been) you are slightly unclear on what this investigation was about this part of the book is a very complete account. The bottom line is that Clinton was very careless in using an unclassified email server. That conclusion was easily reached but it took the FBI much longer to trawl through the emails before being able to declare that there was nothing further to the whole issue. Comey reported the closure of the investigation to Congress in July 2016. But two weeks before the 2016 election, the investigation had to be re-opened because further emails were found on another laptop and Comey had to decide whether to inform Congress the investigation was being re-opened. He chose to do so and it is this that Clinton and others believe cost the Democrats the election. Should he have waited until the reopened investigation was complete? That might have resulted in Clinton being elected and then the public finding out she was about to be indicted.
I feel there is an unanswered question lurking over this reopening of the investigation: Comey says he had to make this public because the ongoing examination was projected to take weeks yet, in the event, it was completed before the election; had that been known why could the announcement not have been delayed until the investigation was complete?
Donald Trump enters only in the final stages of the book but it is this part of the book that has attracted the most attention. In some ways though, one can read the previous part of the book as setting the scene for Comey's withering criticism of the US President. Comey has constructed a number of ethical principles based on leaders who have influenced his own life and we know, as the moment approaches, that Trump is going to fall very far short of those standards. And, for once, Trump does not disappoint us.
I write this as one who thinks that Donald Trump is a peculiarly awful individual and president. But, of course, some Republicans will not agree. The attacks on Comey have already begun and are being spearheaded by the web site lyincomey.com. I've just spent some time perusing this site and found that its rebuttals are weak and ludicrous. So I think A Higher Loyalty is a very credible attack on the Trump presidency and will only add to the maelstrom of difficulties now swirling around it.
Friday, 6 April 2018
Prime conjunctions, and ruling families
This is positively my last post on prime conjunctions and I expect it to be read by nerds only. My purpose is to give two concrete examples of the more technical discussions in my two previous posts on prime conjunctions.
Let's begin with the children of Elizabeth II. They are (listed not by age but by the order in the year that their birthdays occur):
Let's begin with the children of Elizabeth II. They are (listed not by age but by the order in the year that their birthdays occur):
- Andrew b. 19/2/1960
- Edward b. 10/3/1964
- Anne b. 15/8/1950
- Charles b. 14/11/1948
Their ages at the beginning of 2018 were 57, 53, 67, 69. There's a stroke of luck - they are all odd. Indeed they are odd during the time interval 14/11/1999 to 18/2/2000. Such an odd conjunction period occurs every two years so maybe we shall find many prime conjunctions. Sadly, that set of ages has remainders 0, 2, 1, 0 on division by 3. In other words the 3-condition of my previous post fails - whenever the ages are odd, therefore, at least one age will be divisible by 3. So the only chance of a prime conjunction is when one of the is 3 itself and that would have to Edward's age. When he was 3 during the odd conjunction period the set of ages was 7, 3, 17, 19 and they are all prime. So the Royal siblings have had a prime conjunction (which they no doubt celebrated uproariously) but there will never be another.
What about 5 individuals who I shall call (in the order of their birthdays throughout the year)
- Barron b. 20/3/2006
- Melania b. 26/4/1970
- Donald b. 14/6/1946
- Tiffany b. 13/10/93
- Ivanka b. 30/10/1981
At the beginning of 2018 their ages are 11, 47, 71, 36, 24. Oh dear - not all prime and neither are they all odd. However they do have the property that they are bunch of odds followed by a bunch of evens and so we know that eventually they will have an odd conjunction. The nearest odd conjunctive period is 14/6/2017 to 29/10/2017 when their ages are 11, 47, 71, 35, 23. Nearly all prime but not quite - maybe this will also prove impossible.
Since there are 5 people in this case we have to check both the 3-condition and the 5-condition. The 3-residues are 2, 2, 2, 2, 2 while the 5-residues are 1, 2, 1, 0, 3. Both conditions hold! So Dickson's conjecture would predict that, not only will these 5 individuals have a prime conjunction, they will have infinitely many. How do we find them?
Their earliest prime conjunction occurred when the ages were 7, 43, 67, 31, 19. To find later prime conjunctions we must add a number d to all of them that has the properties
- d is even
- d has remainder 0 or 1 when divided by 3
- d is exactly divisible by 5
By a procedure called the Chinese Remainder Theorem these 3 conditions are equivalent to the condition d has remainder 0 or 10 when divided by 30. So the choices for d are 0, 10, 30, 40, 60, 70 etc. In fact d = 30 works (37, 73, 97, 61, 79). The next successful value of d is 40 and I'll leave you to find others.
Wednesday, 14 March 2018
Prime conjunctions and Dickson's conjecture
Way back in 2013 I blogged about "Prime Conjunctions". If you want to get the most out of this posting you will need to read that article first (use the search box) but I will supply some background here anyway.
This all started when one day I noticed that all my children's ages were prime numbers (and, of course, they remained like that until one of them had a birthday and spoilt everything). Not every set of people are destined to enjoy such a prime conjunction but how lucky do they have to be to have one? Since most prime numbers are odd it is unsurprising that a major thing to investigate is whether there will be a period when all their ages are odd and this was the main focus of my previous posting. But before recounting that story let's briefly consider the case that the prime 2 might occur as part of a prime conjunction. To determine whether that is possible all you need do is note the ages of your other children in the full year of one of your children being two; throughout the year these ages will change slightly as your other children have their birthdays and you see whether they ever become prime together. You have to do this for each child and the period in which they are two.
Having dispensed with the case that a prime conjunction might involve the prime number 2 we shall, from now on, just consider whether a prime conjunction with odd primes only can occur. So we shall begin by considering whether your children can have an odd conjunction: a period when all their ages are odd. It is not difficult to find the condition. If you list their ages at the beginning of the year in the order in which their birthdays occur you can look forward to them all being odd if that list is either a bunch of odds followed by a bunch of evens or a bunch of evens followed by a bunch of odds.
For example if on 1 January the ages in birthday order through the year are 10, 6, 9 then when the 6 year old turns 7 the ages will be 11, 7, 9 (because the 10 year old has already turned 11). On the other hand if their ages on 1 January had been 10, 5, 8 there is never a period when all their ages are odd.
It is also easy to see that even when an odd conjunction is possible there is only one period between birthdays when it occurs (in the example 10, 6, 9 that is the period in the year when the first two birthdays have occurred but the third not yet - and this is in every other year).
Essentially then if we are given a set of people we can tell if an odd conjunction is possible and, if it is possible, we can determine the unique interval in the year when it occurs. I shall mention in passing here that, obviously, if an odd conjunction occurs, then other odd conjunctions occur at two year intervals so once we have one odd conjunction we shall have infinitely many. That suggests a related question: if there is a prime conjunction are there infinitely many? That may seem like a much stronger requirement but we shall see that it really isn't. So, for the moment, let's consider whether there are an infinite number of prime conjunctions. At the end of this article I'll return to the original question.
So let's assume you have carried out the calculation above and found that your children do have an odd conjunction. If there are going to be prime conjunctions then they must occur in the same period of the year when the odd conjunctions occur. The mathematical expression of the question therefore is: given k odd numbers a1, a2, ..., ak can we find some number n (indeed, an infinite collection of numbers n) to add to all of them making them prime? These numbers n will, of course, all be even.
As an easy test case consider divisibility by 3. Is it possible that no matter what value n we add to the set of ages we shall always find one that is a multiple of 3? Yes, indeed! The condition is simply that among the k remainders when the ak are divided by 3 all the possible remainders 0, 1 and 2 occur; if so this condition must persist when a number n is added. For example the ages 7, 9, 11 never become prime if we a positive number n to all of them as their remainders on division by 3 are 1, 0 and 2. But notice also that if only two (or one) possible remainders occurred (as, for example, 7, 9, 13) then there will be an infinite set of values n (1, 4, 7, 10, ... ) where none of a1 + n, a2 + n, ..., ak + n are divisible by 3.
A similar condition must hold for every prime p: if the remainders when a1, a2, ..., ak
are divided by p do not include every possible remainder 0, 1, ..., p-1 then there are infinitely many values of n for which every sum a1 + n, a2 + n, ..., ak + n is not divisible by p. It's convenient to give a name to this phenomenon.We shall say that a1, a2, ..., ak satisfies the p-condition if, among the remainders on dividing a1, a2, ..., ak by p, at least one remainder does not occur. The point is that, when the p-condition holds, then there will be infinitely many values of n for which the set al + n, a2 + n,...,ak + n contains a number not divisible by p. So if we are looking for an infinite number of prime conjunctions we want the p-condition to hold for all values of p. This seems like a strong condition to require but it isn't: it's easy to see that the p-condition almost always holds. Indeed it holds for all p>k (because then k remainders cannot exhaust the set of all possible remainders).
So here's the $64000 question. Well, actually, it's more like the $64000000000 question. If the p-condition always holds will we necessarily have a prime conjunction? This is where Dickson's conjecture enters the scene. It states: Let a1, a2, ..., ak and b1, b2, ..., bk be positive integers. Suppose that there is no prime p which divides the product (al + nb1)(a2 + nb2)...(ak + nbk) for all values of n. Then there are infinitely many values of n for which all of al + nb1, a2 + nb2,...,ak + nbk are prime.
Let's restate that conjecture in the special case that all the bi are equal to 1. It then states: suppose there is no prime p that divides at least one of al + n, a2 + n, ... , ak + n for all values of n. Then, for infinitely many values of n, all of al + n, a2 + n, ...,, ak + n are prime. To put this in the language we have been using the conjecture says: if the p-condition holds for all primes p then al, a2 ,..., ak have infinitely many prime conjunctions.
Thus, assuming Dickson's conjecture, the bottom line on how to find a prime conjunctions (if they exist) given a set of ages a1, ..., ak on 1 January is the following:
Of course the big downside of all of this is that we don't know whether Dickson's conjecture is indeed true! A proof of it is not likely to be found any time soon. Notice that the case k=2 and with n and n+2 is the twin primes conjecture: whether there are infinitely many primes differing by 2. The twin primes conjecture is a famous unproven conjecture and widely thought to be true. Clearly Dickson's conjecture is an even tougher nut.
Finally, let's return to the original question: does there exist at least one prime conjunction? One case that may arise is when one of the primes occurring in the conjunction is 2: it's easy to check such cases. So let's consider just odd primes again. We shall need the condition that odd conjunctions exist just as before. Also, we can rely on Dickson's conjecture if the p-condition holds for all odd primes. So the only cases where we might have a prime conjunction not covered by the analysis above is when the p-condition fails for one or more primes. But such a prime p is necessarily no more than k so there are only a finite number of primes to consider. Here, in any prime conjunction, one of the terms must be divisible by p and so must be p itself. So the prime conjunctions in question must have some prime no more than k and these can be inspected on a case by case basis.
For example, 2, 5, 7 is a prime conjunction which never reoccurs. And 3,5,7 is another because the 3-condition fails.
This all started when one day I noticed that all my children's ages were prime numbers (and, of course, they remained like that until one of them had a birthday and spoilt everything). Not every set of people are destined to enjoy such a prime conjunction but how lucky do they have to be to have one? Since most prime numbers are odd it is unsurprising that a major thing to investigate is whether there will be a period when all their ages are odd and this was the main focus of my previous posting. But before recounting that story let's briefly consider the case that the prime 2 might occur as part of a prime conjunction. To determine whether that is possible all you need do is note the ages of your other children in the full year of one of your children being two; throughout the year these ages will change slightly as your other children have their birthdays and you see whether they ever become prime together. You have to do this for each child and the period in which they are two.
Having dispensed with the case that a prime conjunction might involve the prime number 2 we shall, from now on, just consider whether a prime conjunction with odd primes only can occur. So we shall begin by considering whether your children can have an odd conjunction: a period when all their ages are odd. It is not difficult to find the condition. If you list their ages at the beginning of the year in the order in which their birthdays occur you can look forward to them all being odd if that list is either a bunch of odds followed by a bunch of evens or a bunch of evens followed by a bunch of odds.
For example if on 1 January the ages in birthday order through the year are 10, 6, 9 then when the 6 year old turns 7 the ages will be 11, 7, 9 (because the 10 year old has already turned 11). On the other hand if their ages on 1 January had been 10, 5, 8 there is never a period when all their ages are odd.
It is also easy to see that even when an odd conjunction is possible there is only one period between birthdays when it occurs (in the example 10, 6, 9 that is the period in the year when the first two birthdays have occurred but the third not yet - and this is in every other year).
Essentially then if we are given a set of people we can tell if an odd conjunction is possible and, if it is possible, we can determine the unique interval in the year when it occurs. I shall mention in passing here that, obviously, if an odd conjunction occurs, then other odd conjunctions occur at two year intervals so once we have one odd conjunction we shall have infinitely many. That suggests a related question: if there is a prime conjunction are there infinitely many? That may seem like a much stronger requirement but we shall see that it really isn't. So, for the moment, let's consider whether there are an infinite number of prime conjunctions. At the end of this article I'll return to the original question.
So let's assume you have carried out the calculation above and found that your children do have an odd conjunction. If there are going to be prime conjunctions then they must occur in the same period of the year when the odd conjunctions occur. The mathematical expression of the question therefore is: given k odd numbers a1, a2, ..., ak can we find some number n (indeed, an infinite collection of numbers n) to add to all of them making them prime? These numbers n will, of course, all be even.
As an easy test case consider divisibility by 3. Is it possible that no matter what value n we add to the set of ages we shall always find one that is a multiple of 3? Yes, indeed! The condition is simply that among the k remainders when the ak are divided by 3 all the possible remainders 0, 1 and 2 occur; if so this condition must persist when a number n is added. For example the ages 7, 9, 11 never become prime if we a positive number n to all of them as their remainders on division by 3 are 1, 0 and 2. But notice also that if only two (or one) possible remainders occurred (as, for example, 7, 9, 13) then there will be an infinite set of values n (1, 4, 7, 10, ... ) where none of a1 + n, a2 + n, ..., ak + n are divisible by 3.
A similar condition must hold for every prime p: if the remainders when a1, a2, ..., ak
are divided by p do not include every possible remainder 0, 1, ..., p-1 then there are infinitely many values of n for which every sum a1 + n, a2 + n, ..., ak + n is not divisible by p. It's convenient to give a name to this phenomenon.We shall say that a1, a2, ..., ak satisfies the p-condition if, among the remainders on dividing a1, a2, ..., ak by p, at least one remainder does not occur. The point is that, when the p-condition holds, then there will be infinitely many values of n for which the set al + n, a2 + n,...,ak + n contains a number not divisible by p. So if we are looking for an infinite number of prime conjunctions we want the p-condition to hold for all values of p. This seems like a strong condition to require but it isn't: it's easy to see that the p-condition almost always holds. Indeed it holds for all p>k (because then k remainders cannot exhaust the set of all possible remainders).
So here's the $64000 question. Well, actually, it's more like the $64000000000 question. If the p-condition always holds will we necessarily have a prime conjunction? This is where Dickson's conjecture enters the scene. It states: Let a1, a2, ..., ak and b1, b2, ..., bk be positive integers. Suppose that there is no prime p which divides the product (al + nb1)(a2 + nb2)...(ak + nbk) for all values of n. Then there are infinitely many values of n for which all of al + nb1, a2 + nb2,...,ak + nbk are prime.
Let's restate that conjecture in the special case that all the bi are equal to 1. It then states: suppose there is no prime p that divides at least one of al + n, a2 + n, ... , ak + n for all values of n. Then, for infinitely many values of n, all of al + n, a2 + n, ...,, ak + n are prime. To put this in the language we have been using the conjecture says: if the p-condition holds for all primes p then al, a2 ,..., ak have infinitely many prime conjunctions.
Thus, assuming Dickson's conjecture, the bottom line on how to find a prime conjunctions (if they exist) given a set of ages a1, ..., ak on 1 January is the following:
- Determine whether there is an interval in the next two year period when all the ages are odd. If so replace the ages by this new set.
- For the primes p≤k see if the p-condition holds
Of course the big downside of all of this is that we don't know whether Dickson's conjecture is indeed true! A proof of it is not likely to be found any time soon. Notice that the case k=2 and with n and n+2 is the twin primes conjecture: whether there are infinitely many primes differing by 2. The twin primes conjecture is a famous unproven conjecture and widely thought to be true. Clearly Dickson's conjecture is an even tougher nut.
Finally, let's return to the original question: does there exist at least one prime conjunction? One case that may arise is when one of the primes occurring in the conjunction is 2: it's easy to check such cases. So let's consider just odd primes again. We shall need the condition that odd conjunctions exist just as before. Also, we can rely on Dickson's conjecture if the p-condition holds for all odd primes. So the only cases where we might have a prime conjunction not covered by the analysis above is when the p-condition fails for one or more primes. But such a prime p is necessarily no more than k so there are only a finite number of primes to consider. Here, in any prime conjunction, one of the terms must be divisible by p and so must be p itself. So the prime conjunctions in question must have some prime no more than k and these can be inspected on a case by case basis.
For example, 2, 5, 7 is a prime conjunction which never reoccurs. And 3,5,7 is another because the 3-condition fails.
Subscribe to:
Posts (Atom)