## A series of series

DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

### A series of series

Here's a puzzle I thought up today.

How was the following complete series generated?

2, 3, 3, 3, 3

Well, obviously there are many ways it could have been generated but I'll tell you that the series is purely mathematical in nature and depends only on the first number in the series. Here's another one:

7, 1, 9, 3, 3, 3

An infinite number of series could be generated. I suspect all these series will be of finite length but haven't tried to prove it. Perhaps that could be an extra exercise after the nature of the series has been found by you guys.
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
I suspect this puzzle is quite difficult. I'll therefore give a major clue by providing a link I used when generating the series:

DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
A few more series:

3, 1, 1, 9, 3

5, 3

11, 3

What do the first numbers in the series have in common? What do the subsequent numbers in the series have in common? How important are commas, really?

BTW, I just noticed something interesting in each of the series so far. They all end in a 3. I wonder if that is always the case.
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
I can't see why the 2 sequence doesn't go:

2, 9, 3, 9, 9, 9, 9, 9<br><br><table><tr bgcolor="#c0c0e0"><td> Spoiler - 'select' text using mouse, or press Ctrl-A to reveal. </td></tr><tr bgcolor="white"><td><br>Adding a digit to the end of the number each time, the numbers remain prime, so:
2, 29, 293, 2939, 29399, 293999, 2939999 and 29399999 are all prime
but there is no 9 digit prime 29399999x<br><br>
</td></tr></table><br>
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
ceptimus wrote:I can't see why the 2 sequence doesn't go:

2, 9, 3, 9, 9, 9, 9, 9<br><br><table><tr bgcolor="#c0c0e0"><td> Spoiler - 'select' text using mouse, or press Ctrl-A to reveal. </td></tr><tr bgcolor="white"><td><br>Adding a digit to the end of the number each time, the numbers remain prime, so:
2, 29, 293, 2939, 29399, 293999, 2939999 and 29399999 are all prime
but there is no 9 digit prime 29399999x<br><br>
</td></tr></table><br>
The reason is because my algorithm (in my head) was to always pick the lowest solution, when there were more than one possible solution.

However, since you got the basic algorithm, can you prove that any series derived from this algorithm will always be finite?

(The stuff I mentioned earlier about how every series always seemed to end on a 3 is not true. I found a counterexample).
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
I picked the longest solution, rather than the lowest. Whenever there is a choice, track all branches, and follow the one that lasts longest.

I think it's pretty clear that the series will always be finite. In base 10, the last digit of a prime (greater than 5) can never be 0, 2, 4, 5, 6, or 8. The sum of the individual digits can't be a multiple of three either. The digits 3 and 9 tend to be favored - adding a 1 or 7 at the end is more likely to make the number divisible by 3. Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof - merely arm waving.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
ceptimus wrote:... Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof - merely arm waving.
Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.

Example, for N=3, one such non-prime sequence is

{ 14, 15, 16 }

But that is not a proof of your conjecture. Can we call it that?
Ceptimus's Conjecture: For any integer base b>1, there is a largest prime P such that P*b+m is also prime, for any 0<m<b.
Or have I misunderstood what you meant? I would wager that the conjecture is false, but I have no proof of that either.

In base two, perhaps a negation of that could be called the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.
Skeptoid
Posts: 1296
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin
xouper wrote:Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.
Okay, N=7.6 x 10<sup>7</sup> +1. :shock: :D

I'll settle for a proof. Number theory is cool. 8)
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
Skeptoid wrote:
xouper wrote:Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.
Okay, N=7.6 x 10<sup>7</sup> +1. :shock: :D

I'll settle for a proof. Number theory is cool. 8)
Let M = (N+1)!

Here's a sequence of N consecutive non-primes:

{ M+2, M+3, M+4, M+5, ..., M+N, M+N+1 }

See, for example:
http://en.wikipedia.org/wiki/Prime_number#Prime_gaps

Notice that compared to M, the prime gap specified by N is relatively small.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
xouper wrote:... the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.
Now that I think about it for a minute, that can't possibly be true for m>2, since 1#m can be prime only if m is prime, and if m is prime, then m+1 cannot be prime, and thus 1#(m+1) cannot be prime.

OK, that proves Ceptimus's Conjecture for base two.
Skeptoid
Posts: 1296
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin
Thanks, xoup. I find it fascinating that there can be an arbitrarily large gap between successive primes while at the same time there are an infinite number of prime pairs where the gap = 1 (if the Twin Prime Conjecture is true).
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK
xouper wrote:
ceptimus wrote:... Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof - merely arm waving.
Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.

Example, for N=3, one such non-prime sequence is

{ 14, 15, 16 }

But that is not a proof of your conjecture. Can we call it that?
Ceptimus's Conjecture: For any integer base b>1, there is a largest prime P such that P*b+m is also prime, for any 0<m<b.
Or have I misunderstood what you meant? I would wager that the conjecture is false, but I have no proof of that either.

In base two, perhaps a negation of that could be called the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.
I don't think that wording of the 'conjecture' quite sums it up (unless I've misunderstood what you meant :) ). I would interpret your wording as saying 'there are no primes bigger than a certain limit where another prime can be generated by adding a single digit', which I also suspect is false. However, I'm not very good at math notation, so I may have misunderstood your wording. The wording should indicate that all the numbers in a series of length q, generated from the 'seed prime' by adding digits one at a time, must also be prime, not just the first one.

For me, a better wording of the 'ceptimus conjecture' (actually it's DanishDynamite's) :D would be:

In any base b > 2, there is no prime P[0] that can generate more than q primes by applying the iteration P[n+1] = P[n] * b + m (where 0 < m < b)

I would hazard a guess that q < (b + Log(base b)(P[0]))
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
I knew this puzzle could lead to interesting things. :)

I agree with ceptimus, though. The "ceptimus conjecture" as described by xouper is not equivalent to the question I posed and I very much suspect this version to be false.

The version given by ceptimus is the one I had in mind.
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
xouper wrote:
xouper wrote:OK, that proves Ceptimus's Conjecture for base two.
Errrmm, not so fast, binary-breath. You forgot about Sophie Germain primes, wherein both P and 2P+1 are prime, which is the same as tacking a one on the end of the binary representation of a prime.

It has not yet been proven that there are only finitely many Sophie Germain primes, so Ceptimus's Conjecture remains unrefuted for base two.

See, for example:
http://en.wikipedia.org/wiki/Sophie_Germain_prime
Well, dang, that'll teach me to poste in haste. :D
xouper
Posts: 11741
Joined: Fri Jun 11, 2004 4:52 am
Title: mere ghost of his former self
ceptimus wrote:DanishDynamite's Conjecture: In any base b>1, there is no prime P[0] that can generate more than q primes by applying the iteration P[n+1] = P[n] * b + m (where 0<m<b)
Yes, that is different from what I proposed.

I had misunderstood and thought that you were saying that at some value W, q would be zero for all P>W, but I see now that you are not saying that. My error.

We can put the number base back to b>1, since it remains an open question whether there are infinitely many Sophie Germain primes.

http://en.wikipedia.org/wiki/Cunningham_chain

Perhaps DD's conjecture becomes: All generalized Cunningham chains are complete.

Actually DD didn't go quite that far, but hey, why not? Generalized Cunningham chains are not restricted to increments less than the number base, only that the increment be relatively prime to the number base.

Also, as I understand it, DanishDynamite chains are slightly different than Cunningham chains in that DD's increment is not fixed for the entire chain.
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen
Interesting stuff, xouper.
Also, as I understand it, DanishDynamite chains are slightly different than Cunningham chains in that DD's increment is not fixed for the entire chain.
Indeed. But it seems to me that if one could prove (and I use your flattering terminology) that all DD chains are complete, one would also have proven that all generalized Cunningham chains, where the increment is less than the number base, are complete.
statisticool
Posts: 145
Joined: Sun Apr 03, 2005 6:25 am

### Re: A series of series

Re: the primes.

I submitted a question to Math Chat some years ago

http://www.maa.org/features/mathchat/ma ... 16_99.html

and it was answered in the next column

http://www.maa.org/features/mathchat/ma ... 06_00.html

The idea, with different terminology, goes back to at least 1968 (snowball primes), but I'm sure people considered it earlier.