A series of series

Stump your fellow simians.
User avatar
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

A series of series

Post by DanishDynamite »

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.

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

Post by DanishDynamite »

I suspect this puzzle is quite difficult. I'll therefore give a major clue by providing a link I used when generating the series:

Don't click here unless you want a major clue

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

Post by DanishDynamite »

A few more series:

3, 1, 1, 9, 3

5, 3

11, 3

Some leading questions:

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.

User avatar
ceptimus
Posts: 1278
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

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>

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

Post by DanishDynamite »

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).

User avatar
ceptimus
Posts: 1278
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

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.

User avatar
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building

Post by xouper »

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.

User avatar
Skeptoid
Posts: 1294
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin

Post by Skeptoid »

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)
[img]http://img170.exs.cx/img170/1125/searsskeptic1wo.gif[/img]

User avatar
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building

Post by xouper »

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.

User avatar
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building

Post by xouper »

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.

User avatar
Skeptoid
Posts: 1294
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin

Post by Skeptoid »

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).
[img]http://img170.exs.cx/img170/1125/searsskeptic1wo.gif[/img]

User avatar
ceptimus
Posts: 1278
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

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]))

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

Post by DanishDynamite »

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.

User avatar
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building

Post by xouper »

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

User avatar
xouper
Posts: 9473
Joined: Fri Jun 11, 2004 4:52 am
Location: has left the building

Post by xouper »

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.

See also Cunningham chains:
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.

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

Post by DanishDynamite »

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.

User avatar
statisticool
Posts: 145
Joined: Sun Apr 03, 2005 6:25 am

Re: A series of series

Post by statisticool »

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.