[math-fun] A prime factor factory
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize? E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done. I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn’t able to do this. Jim Propp
Let a(n) = number of distinct primes produced by starting with the n-th prime p and iterating Jim's process of looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes. Let a(n) = -1 if this produces infinitely many primes. Jim's example, starting with 2, seems to produce nine primes, 2 3 5 7 11 13 19 23 47, so a(1)=9. How does this sequence begin? Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Sat, Jun 16, 2018 at 6:14 PM, James Propp <jamespropp@gmail.com> wrote:
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize?
E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done.
I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn’t able to do this.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If my program is correct, starting with the n-th prime (n<=10^5) the procedure always ends with {3, 5, 7, 11, 13, 19, 23, 47} which is sequence A020575: (In particular the number of primes obtained will always be finite.) Example starting with the the 10000th prime: {104729} {209459} {251, 1669} {3, 7, 53, 503} {3, 5, 7, 19, 53, 107} {3, 5, 7, 11, 13, 43, 107} {3, 5, 7, 11, 23, 29, 43} {3, 5, 7, 11, 23, 29, 47, 59} {3, 5, 7, 11, 17, 19, 23, 47, 59} {3, 5, 7, 11, 13, 17, 19, 23, 47} {3, 5, 7, 11, 13, 19, 23, 47} Let a(n) = number of distinct primes produced by starting with the n-th
prime p and iterating Jim's process of looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes. Let a(n) = -1 if this produces infinitely many primes.
Jim's example, starting with 2, seems to produce nine primes, 2 3 5 7 11 13 19 23 47, so a(1)=9.
How does this sequence begin?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 6:14 PM, James Propp <jamespropp@gmail.com> wrote:
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize?
E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done.
I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn’t able to do this.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yup, I get the same thing as Edwin. Among the first 1M primes, the largest number of distinct primes that ever appear when doing Jim's expansion is 37, a maximum first attained by 9453569 (the 630705th prime). The set of primes that appear, closed under the factors-of-2p+1 operation, is {3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59, 67, 71, 79, 83, 107, 167, 179, 359, 443, 719, 809, 887, 1163, 1439, 1619, 1889, 2833, 2879, 3779, 7559, 15581, 23371, 9453569}. For Neil, the first 100 terms of the sequence of total-number-of-primes-seen is: 9, 8, 8, 8, 8, 8, 9, 8, 8, 11, 9, 9, 12, 12, 8, 14, 10, 13, 9, 9, 9, 15, 11, 17, 9, 12, 9, 13, 10, 10, 10, 12, 9, 10, 9, 13, 9, 11, 10, 12, 16, 9, 12, 13, 16, 9, 9, 10, 9, 10, 11, 11, 9, 16, 10, 11, 9, 10, 10, 10, 9, 10, 13, 18, 9, 11, 10, 9, 11, 12, 13, 15, 9, 12, 9, 11, 13, 15, 10, 9, 11, 11, 11, 10, 11, 11, 13, 14, 10, 10, 10, 10, 9, 12, 10, 15, 17, 10, 13, 9 Quickie mma code to compute this stuff: propp1[p_] := propp1[p] = #[[1]]& /@ FactorInteger[2*p+1] propp[p_Integer] := propp[{p}] propp[s_List] := propp[s, Union[s, Union @@ propp1 /@ s]] propp[s_, t_] := If[s==t, s, If[Length[t]>1000, OVERFLOW[t], propp[t]]] Then propp[9453569] is the length=37 set of primes above, and Table[Length[propp[Prime[n]]], {n,100}] is the sequence. --Michael On Sat, Jun 16, 2018 at 9:57 PM W. Edwin Clark <wclark@mail.usf.edu> wrote:
If my program is correct, starting with the n-th prime (n<=10^5) the procedure always ends with {3, 5, 7, 11, 13, 19, 23, 47} which is sequence A020575: (In particular the number of primes obtained will always be finite.)
Example starting with the the 10000th prime:
{104729} {209459} {251, 1669} {3, 7, 53, 503} {3, 5, 7, 19, 53, 107} {3, 5, 7, 11, 13, 43, 107} {3, 5, 7, 11, 23, 29, 43} {3, 5, 7, 11, 23, 29, 47, 59} {3, 5, 7, 11, 17, 19, 23, 47, 59} {3, 5, 7, 11, 13, 17, 19, 23, 47} {3, 5, 7, 11, 13, 19, 23, 47}
Let a(n) = number of distinct primes produced by starting with the n-th
prime p and iterating Jim's process of looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes. Let a(n) = -1 if this produces infinitely many primes.
Jim's example, starting with 2, seems to produce nine primes, 2 3 5 7 11 13 19 23 47, so a(1)=9.
How does this sequence begin?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 6:14 PM, James Propp <jamespropp@gmail.com> wrote:
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize?
E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done.
I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn’t able to do this.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
The sequence is now https://oeis.org/A305382 Comments welcomed. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Sat, Jun 16, 2018 at 10:24 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Yup, I get the same thing as Edwin.
Among the first 1M primes, the largest number of distinct primes that ever appear when doing Jim's expansion is 37, a maximum first attained by 9453569 (the 630705th prime). The set of primes that appear, closed under the factors-of-2p+1 operation, is {3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59, 67, 71, 79, 83, 107, 167, 179, 359, 443, 719, 809, 887, 1163, 1439, 1619, 1889, 2833, 2879, 3779, 7559, 15581, 23371, 9453569}.
For Neil, the first 100 terms of the sequence of total-number-of-primes-seen is: 9, 8, 8, 8, 8, 8, 9, 8, 8, 11, 9, 9, 12, 12, 8, 14, 10, 13, 9, 9, 9, 15, 11, 17, 9, 12, 9, 13, 10, 10, 10, 12, 9, 10, 9, 13, 9, 11, 10, 12, 16, 9, 12, 13, 16, 9, 9, 10, 9, 10, 11, 11, 9, 16, 10, 11, 9, 10, 10, 10, 9, 10, 13, 18, 9, 11, 10, 9, 11, 12, 13, 15, 9, 12, 9, 11, 13, 15, 10, 9, 11, 11, 11, 10, 11, 11, 13, 14, 10, 10, 10, 10, 9, 12, 10, 15, 17, 10, 13, 9
Quickie mma code to compute this stuff:
propp1[p_] := propp1[p] = #[[1]]& /@ FactorInteger[2*p+1] propp[p_Integer] := propp[{p}] propp[s_List] := propp[s, Union[s, Union @@ propp1 /@ s]] propp[s_, t_] := If[s==t, s, If[Length[t]>1000, OVERFLOW[t], propp[t]]]
Then propp[9453569] is the length=37 set of primes above, and Table[Length[propp[Prime[n]]], {n,100}] is the sequence.
--Michael
On Sat, Jun 16, 2018 at 9:57 PM W. Edwin Clark <wclark@mail.usf.edu> wrote:
If my program is correct, starting with the n-th prime (n<=10^5) the procedure always ends with {3, 5, 7, 11, 13, 19, 23, 47} which is sequence A020575: (In particular the number of primes obtained will always be finite.)
Example starting with the the 10000th prime:
{104729} {209459} {251, 1669} {3, 7, 53, 503} {3, 5, 7, 19, 53, 107} {3, 5, 7, 11, 13, 43, 107} {3, 5, 7, 11, 23, 29, 43} {3, 5, 7, 11, 23, 29, 47, 59} {3, 5, 7, 11, 17, 19, 23, 47, 59} {3, 5, 7, 11, 13, 17, 19, 23, 47} {3, 5, 7, 11, 13, 19, 23, 47}
Let a(n) = number of distinct primes produced by starting with the n-th
prime p and iterating Jim's process of looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes. Let a(n) = -1 if this produces infinitely many primes.
Jim's example, starting with 2, seems to produce nine primes, 2 3 5 7 11 13 19 23 47, so a(1)=9.
How does this sequence begin?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 6:14 PM, James Propp <jamespropp@gmail.com> wrote:
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize?
E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done.
I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn’t able to do this.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This matter seems to be related to Cunningham chains <https://en.wikipedia.org/wiki/Cunningham_chain>--sequences of primes p_i such that p_{i+1} = 2p_{i} + 1. Example, starting with a long Cunningham chain (*of the first kind*) from the above link, the Propp procedure gives: 0, {2759832934171386593519} 1, {5519665868342773187039} 2, {11039331736685546374079} 3, {22078663473371092748159} 4, {44157326946742185496319} 5, {88314653893484370992639} 6, {176629307786968741985279} 7, {353258615573937483970559} 8, {706517231147874967941119} 9, {1413034462295749935882239} 10, {2826068924591499871764479} 11, {5652137849182999743528959} 12, {11304275698365999487057919} 13, {22608551396731998974115839} 14, {45217102793463997948231679} 15, {90434205586927995896463359} 16, {180868411173855991792926719} 17, {853, 7649, 55442017698213695587} 18, {3, 5, 7, 11, 137, 191, 569, 15299, 733775318911} 19, {3, 5, 7, 11, 17, 23, 37, 67, 211, 383, 827, 38713, 59887} 20, {3, 5, 7, 11, 13, 23, 47, 59, 331, 1229, 1597} 21, {3, 5, 7, 11, 13, 17, 19, 23, 47, 71, 2459} 22, {3, 5, 7, 11, 13, 19, 23, 47, 4919} 23, {3, 5, 7, 11, 13, 19, 23, 47, 9839} 24, {3, 5, 7, 11, 13, 19, 23, 47, 1789} 25, {3, 5, 7, 11, 13, 19, 23, 47, 1193} 26, {3, 5, 7, 11, 13, 19, 23, 31, 47} 27, {3, 5, 7, 11, 13, 19, 23, 47} Note we still reach the set {3, 5, 7, 11, 13, 19, 23, 47} It is conjectured that there are Cunningham chains of length k for all positive integers k. Is there a reason that one could not have a Cunningham chain of infinite length? On Sun, Jun 17, 2018 at 10:00 AM, Neil Sloane <njasloane@gmail.com> wrote:
The sequence is now https://oeis.org/A305382 Comments welcomed.
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 10:24 PM, Michael Kleber <michael.kleber@gmail.com
wrote:
Yup, I get the same thing as Edwin.
Among the first 1M primes, the largest number of distinct primes that ever appear when doing Jim's expansion is 37, a maximum first attained by 9453569 (the 630705th prime). The set of primes that appear, closed under the factors-of-2p+1 operation, is {3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59, 67, 71, 79, 83, 107, 167, 179, 359, 443, 719, 809, 887, 1163, 1439, 1619, 1889, 2833, 2879, 3779, 7559, 15581, 23371, 9453569}.
For Neil, the first 100 terms of the sequence of total-number-of-primes-seen is: 9, 8, 8, 8, 8, 8, 9, 8, 8, 11, 9, 9, 12, 12, 8, 14, 10, 13, 9, 9, 9, 15, 11, 17, 9, 12, 9, 13, 10, 10, 10, 12, 9, 10, 9, 13, 9, 11, 10, 12, 16, 9, 12, 13, 16, 9, 9, 10, 9, 10, 11, 11, 9, 16, 10, 11, 9, 10, 10, 10, 9, 10, 13, 18, 9, 11, 10, 9, 11, 12, 13, 15, 9, 12, 9, 11, 13, 15, 10, 9, 11, 11, 11, 10, 11, 11, 13, 14, 10, 10, 10, 10, 9, 12, 10, 15, 17, 10, 13, 9
Quickie mma code to compute this stuff:
propp1[p_] := propp1[p] = #[[1]]& /@ FactorInteger[2*p+1] propp[p_Integer] := propp[{p}] propp[s_List] := propp[s, Union[s, Union @@ propp1 /@ s]] propp[s_, t_] := If[s==t, s, If[Length[t]>1000, OVERFLOW[t], propp[t]]]
Then propp[9453569] is the length=37 set of primes above, and Table[Length[propp[Prime[n]]], {n,100}] is the sequence.
--Michael
On Sat, Jun 16, 2018 at 9:57 PM W. Edwin Clark <wclark@mail.usf.edu> wrote:
If my program is correct, starting with the n-th prime (n<=10^5) the procedure always ends with {3, 5, 7, 11, 13, 19, 23, 47} which is sequence A020575: (In particular the number of primes obtained will always be finite.)
Example starting with the the 10000th prime:
{104729} {209459} {251, 1669} {3, 7, 53, 503} {3, 5, 7, 19, 53, 107} {3, 5, 7, 11, 13, 43, 107} {3, 5, 7, 11, 23, 29, 43} {3, 5, 7, 11, 23, 29, 47, 59} {3, 5, 7, 11, 17, 19, 23, 47, 59} {3, 5, 7, 11, 13, 17, 19, 23, 47} {3, 5, 7, 11, 13, 19, 23, 47}
Let a(n) = number of distinct primes produced by starting with the n-th
prime p and iterating Jim's process of looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes. Let a(n) = -1 if this produces infinitely many primes.
Jim's example, starting with 2, seems to produce nine primes, 2 3 5 7 11 13 19 23 47, so a(1)=9.
How does this sequence begin?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 6:14 PM, James Propp <jamespropp@gmail.com> wrote:
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize?
E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done.
I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn’t able to do this.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Is there a reason that one could not have a Cunningham chain of infinite length?
Yes. Cunningham 2P+1 chains are of bounded length. A chain starting with an odd prime P is limited to P-1 terms: example: 5, 11, 23, 47, 95 The Kth term (counting P itself as K=0) is P * 2^K + (2^K - 1). The chain residues mod P cycle through Mersenne numbers. We can notice that P divides 2^(P-1)-1, so K must fail when K = P-1, as with the 5 example above. A more primitive proof of the limitation on K is to note that the chain rule mod P goes C(k+1) = 2 C(k) + 1, which is a 1-1 function mod P, and therefore a permutation. C(0) = 0 mod P, so 0 is in some loop of residues, and therefore must occur again for some K <= P. Of course this doesn't rule out C chains of arbitrary length -- it just says that any specific chain terminates. Rich --- Quoting "W. Edwin Clark" <wclark@mail.usf.edu>:
This matter seems to be related to Cunningham chains <https://en.wikipedia.org/wiki/Cunningham_chain>--sequences of primes p_i such that p_{i+1} = 2p_{i} + 1. Example, starting with a long Cunningham chain (*of the first kind*) from the above link, the Propp procedure gives:
0, {2759832934171386593519} 1, {5519665868342773187039} 2, {11039331736685546374079} 3, {22078663473371092748159} 4, {44157326946742185496319} 5, {88314653893484370992639} 6, {176629307786968741985279} 7, {353258615573937483970559} 8, {706517231147874967941119} 9, {1413034462295749935882239} 10, {2826068924591499871764479} 11, {5652137849182999743528959} 12, {11304275698365999487057919} 13, {22608551396731998974115839} 14, {45217102793463997948231679} 15, {90434205586927995896463359} 16, {180868411173855991792926719} 17, {853, 7649, 55442017698213695587} 18, {3, 5, 7, 11, 137, 191, 569, 15299, 733775318911} 19, {3, 5, 7, 11, 17, 23, 37, 67, 211, 383, 827, 38713, 59887} 20, {3, 5, 7, 11, 13, 23, 47, 59, 331, 1229, 1597} 21, {3, 5, 7, 11, 13, 17, 19, 23, 47, 71, 2459} 22, {3, 5, 7, 11, 13, 19, 23, 47, 4919} 23, {3, 5, 7, 11, 13, 19, 23, 47, 9839} 24, {3, 5, 7, 11, 13, 19, 23, 47, 1789} 25, {3, 5, 7, 11, 13, 19, 23, 47, 1193} 26, {3, 5, 7, 11, 13, 19, 23, 31, 47} 27, {3, 5, 7, 11, 13, 19, 23, 47}
Note we still reach the set {3, 5, 7, 11, 13, 19, 23, 47}
It is conjectured that there are Cunningham chains of length k for all positive integers k.
Is there a reason that one could not have a Cunningham chain of infinite length?
On Sun, Jun 17, 2018 at 10:00 AM, Neil Sloane <njasloane@gmail.com> wrote:
The sequence is now https://oeis.org/A305382 Comments welcomed.
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 10:24 PM, Michael Kleber <michael.kleber@gmail.com
wrote:
Yup, I get the same thing as Edwin.
Among the first 1M primes, the largest number of distinct primes that ever appear when doing Jim's expansion is 37, a maximum first attained by 9453569 (the 630705th prime). The set of primes that appear, closed under the factors-of-2p+1 operation, is {3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59, 67, 71, 79, 83, 107, 167, 179, 359, 443, 719, 809, 887, 1163, 1439, 1619, 1889, 2833, 2879, 3779, 7559, 15581, 23371, 9453569}.
For Neil, the first 100 terms of the sequence of total-number-of-primes-seen is: 9, 8, 8, 8, 8, 8, 9, 8, 8, 11, 9, 9, 12, 12, 8, 14, 10, 13, 9, 9, 9, 15, 11, 17, 9, 12, 9, 13, 10, 10, 10, 12, 9, 10, 9, 13, 9, 11, 10, 12, 16, 9, 12, 13, 16, 9, 9, 10, 9, 10, 11, 11, 9, 16, 10, 11, 9, 10, 10, 10, 9, 10, 13, 18, 9, 11, 10, 9, 11, 12, 13, 15, 9, 12, 9, 11, 13, 15, 10, 9, 11, 11, 11, 10, 11, 11, 13, 14, 10, 10, 10, 10, 9, 12, 10, 15, 17, 10, 13, 9
Quickie mma code to compute this stuff:
propp1[p_] := propp1[p] = #[[1]]& /@ FactorInteger[2*p+1] propp[p_Integer] := propp[{p}] propp[s_List] := propp[s, Union[s, Union @@ propp1 /@ s]] propp[s_, t_] := If[s==t, s, If[Length[t]>1000, OVERFLOW[t], propp[t]]]
Then propp[9453569] is the length=37 set of primes above, and Table[Length[propp[Prime[n]]], {n,100}] is the sequence.
--Michael
On Sat, Jun 16, 2018 at 9:57 PM W. Edwin Clark <wclark@mail.usf.edu> wrote:
If my program is correct, starting with the n-th prime (n<=10^5) the procedure always ends with {3, 5, 7, 11, 13, 19, 23, 47} which is sequence A020575: (In particular the number of primes obtained will always be finite.)
Example starting with the the 10000th prime:
{104729} {209459} {251, 1669} {3, 7, 53, 503} {3, 5, 7, 19, 53, 107} {3, 5, 7, 11, 13, 43, 107} {3, 5, 7, 11, 23, 29, 43} {3, 5, 7, 11, 23, 29, 47, 59} {3, 5, 7, 11, 17, 19, 23, 47, 59} {3, 5, 7, 11, 13, 17, 19, 23, 47} {3, 5, 7, 11, 13, 19, 23, 47}
Let a(n) = number of distinct primes produced by starting with the n-th
prime p and iterating Jim's process of looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes. Let a(n) = -1 if this produces infinitely many primes.
Jim's example, starting with 2, seems to produce nine primes, 2 3 5 7 11 13 19 23 47, so a(1)=9.
How does this sequence begin?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Sat, Jun 16, 2018 at 6:14 PM, James Propp <jamespropp@gmail.com> wrote:
Given any prime p, we can look at all the prime factors of 2p+1, and then perform the same process (double, add 1, find all prime factors) with those primes, and so on; must the process eventually stabilize?
E.g.: 2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19 19 -> 39=3*13 3 -> 7 -> 15=3*5 13 -> 27=3*3*3 Done.
I looked at a variant where one uses 2p-1 instead of 2p+1; it appears to lead to closure a lot more rapidly. For the 2p-1 version, I was able to check in my head that all primes under 100 lead to closure; for the 2p+1 version, I wasn?t able to do this.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
James Propp -
Michael Kleber -
Neil Sloane -
rcs@xmission.com -
W. Edwin Clark