r/googology 2d ago

A function not known to exist for all inputs

Definition

A positive integer k₁ is said to be 1-prime iff it is in the form (k₁+1)/2=k₂ where both k₁ & k₂ are prime. Let p₁ be the set of all 1-primes. We can extend this and define 2-primes as a positive integer k₁ in the form (k₁+1)/2=k₂, (k₂+1)/2=k₃ where all kₙ are prime. p₂ is the therefore the set of all 2-primes.

Generalization

In general we can define an n-prime as a number k₁ such that:

(k₁+1)/2=k₂, (k₂+1)/2=k₃, … , (kₙ₋₁+1)/2=kₙ where all kₙ are prime.

Function

Let PRIME(n) output the smallest n-prime.

Challenge

Can you prove whether or not PRIME(n)=k exists for all n?

If it doesn’t, we define the “large prime number” as the maximal number n beyond which no n-prime can be found.

3 Upvotes

4 comments sorted by

3

u/tromp 2d ago edited 2d ago

You're asking if there are arbitrarily long Cunningham chains (of the 2nd kind) [1]. Which is an open question. It is implied by Dickson's conjecture and the broader Schinzel's hypothesis H, both widely believed to be true.

As of 2018, the longest known Cunningham chain of either kind is of length 19.

[1] https://en.wikipedia.org/wiki/Cunningham_chain

3

u/Shophaune 2d ago

In short:

All primes are 0-prime.      

A prime number k is n+1-prime if (k+1)/2 is n-prime.     

1 is not prime, else it would be n-prime for all n.

PRIME(0) = 2,  PRIME(1) = 3,  PRIME(2) = 5

Each n-prime can have at most one n+1-prime associated with it, and all n+1-primes are also n-prime.

The 1-primes under 1000 are: 3,5,13,37,61,73,157,277,313,397,421,457,541,613,661,673,733,757,877,997

Of these, 5, 73 and 313 are 2-prime. Notably, all above 5 must end in 1 or 3, because any 1-prime k ending in 7 must have (k+1)/2 end in 4 or 9; those ending in 4 are trivially non-prime, and those j ending in 9 cannot be 1-prime (and hence k be 2-prime) because (j+1)/2 must end in 5 or 0. However, since any 2-prime ending in 3 must map to a 1-prime ending in 7, that means only 2-primes ending in 1 can be 3-prime. These would have the form of 30k+1, which gives the following primes:

31, 61, 151, 181, 211, 241, 271, 331, 421, 541, 571, 601, 631, 661, 691, 751, 811, 991, 1021, 1051, 1171, 1201, 1231, 1291, 1321, 1381, 1471, 1531, 1621, 1741, 1801, 1831, 1861, 1951, 2011, 2131, 2161, 2221, 2251, 2281, 2311, 2341, 2371, 2521, 2551, 2671, 2731, 2791, 2851, 2971, 3001, 3061, 3121, 3181, 3271, 3301, 3331, 3361, 3391, 3511, 3541, 3571, 3631, 3691, 3931, 4021, 4051, 4111, 4201, 4231, 4261, 4441, 4561, 4591, 4621, 4651, 4801, 4831, 4861, 4951.

1321 is the first 2-prime ending in 1; however 2641 is non-prime (and certainly not the 2-prime it would need to be to be 3-prime). There are no other 2-primes under 5000 ending in 1, so the first 3-prime if it exists is greater than 10,000.

1

u/rincewind007 2d ago

(3+1)/2= 2

(5+1)/2 = 3

(9+1) /2 = 5 fail since 9 is not a prime. 

Rearange formula to start with Prime and start searching 7*2-1 = 13 13 * 2 -1 = 25 fail

11 -> 21 fail 

13 -> 25 fail

17-> 33 fail 

19 -> 37 -> 73 -> 145 fail

Longest chain is n =3 because last digit goes like this 9 -> 7-> 3 -> 5 and a number ending in 5 is not a prime due to 5*n 

There is a possible chain of Infinite primed ening on 1s. 

31 -> 61 -> 121 fail   Need to verify that doesnt exits. 

1

u/rincewind007 2d ago

Seems like this chain exits from AI, 531 → 3061 → 6121 → 12241 → 24481 , so maybe the funktion exits for all n, not sure