Return to Answer

added cyclic example

Source Link

edited May 14 at 18:14

3.1k
1
9
36

85
177
251
base =  2 starting number =  4 current number =  10 iteration count =  1
base =  2 starting number =  4 current number =  21 iteration count =  2
base =  2 starting number =  4 current number =  31 iteration count =  3
base =  2 starting number =  6 current number =  11 iteration count =  1
base =  2 starting number =  8 current number =  11 iteration count =  1
base =  2 starting number =  9 current number =  14 iteration count =  1
base =  2 starting number =  9 current number =  23 iteration count =  2
base =  2 starting number =  10 current number =  21 iteration count =  1
base =  2 starting number =  10 current number =  31 iteration count =  2
base =  2 starting number =  12 current number =  43 iteration count =  1
base =  2 starting number =  14 current number =  23 iteration count =  1
base =  2 starting number =  15 current number =  29 iteration count =  1
base =  2 starting number =  16 current number =  20 iteration count =  1
base =  2 starting number =  16 current number =  85 iteration count =  2
base =  2 starting number =  16 current number =  177 iteration count =  3
base =  2 starting number =  16 current number =  251 iteration count =  4
base =  2 starting number =  18 current number =  46 iteration count =  1
base =  2 starting number =  18 current number =  87 iteration count =  2
base =  2 starting number =  18 current number =  125 iteration count =  3
base =  2 starting number =  18 current number =  23 iteration count =  4
base =  2 starting number =  20 current number =  85 iteration count =  1
base =  2 starting number =  20 current number =  177 iteration count =  2
base =  2 starting number =  20 current number =  251 iteration count =  3
base =  2 starting number =  21 current number =  31 iteration count =  1
base =  2 starting number =  22 current number =  43 iteration count =  1
base =  2 starting number =  24 current number =  47 iteration count =  1
base =  2 starting number =  25 current number =  22 iteration count =  1
base =  2 starting number =  25 current number =  43 iteration count =  2
base =  2 starting number =  26 current number =  45 iteration count =  1
base =  2 starting number =  26 current number =  117 iteration count =  2
base =  2 starting number =  26 current number =  237 iteration count =  3
base =  2 starting number =  26 current number =  463 iteration count =  4
base =  2 starting number =  27 current number =  15 iteration count =  1
base =  2 starting number =  27 current number =  29 iteration count =  2
base =  2 starting number =  28 current number =  87 iteration count =  1
base =  2 starting number =  28 current number =  125 iteration count =  2
base =  2 starting number =  28 current number =  23 iteration count =  3
base =  2 starting number =  30 current number =  93 iteration count =  1
base =  2 starting number =  30 current number =  127 iteration count =  2
base =  2 starting number =  32 current number =  21 iteration count =  1
base =  2 starting number =  32 current number =  31 iteration count =  2
base =  2 starting number =  33 current number =  59 iteration count =  1
base =  2 starting number =  34 current number =  81 iteration count =  1
base =  2 starting number =  34 current number =  28 iteration count =  2
base =  2 starting number =  34 current number =  87 iteration count =  3
base =  2 starting number =  34 current number =  125 iteration count =  4
base =  2 starting number =  34 current number =  23 iteration count =  5
base =  2 starting number =  35 current number =  47 iteration count =  1
base =  2 starting number =  36 current number =  174 iteration count =  1
base =  2 starting number =  36 current number =  381 iteration count =  2
base =  2 starting number =  36 current number =  511 iteration count =  3 
base =  2 starting number =  36 current number =  969 iteration count =

For $n=217$ and for $d=2$ you get as an example a cycle which is not a prime:

SageMath-Script

$$217, 255, 945, 1007, 1269,1007,1269,1007\ldots$$

85
177
251
base =  2 starting number =  4 current number =  10 iteration count =  1
base =  2 starting number =  4 current number =  21 iteration count =  2
base =  2 starting number =  4 current number =  31 iteration count =  3
base =  2 starting number =  6 current number =  11 iteration count =  1
base =  2 starting number =  8 current number =  11 iteration count =  1
base =  2 starting number =  9 current number =  14 iteration count =  1
base =  2 starting number =  9 current number =  23 iteration count =  2
base =  2 starting number =  10 current number =  21 iteration count =  1
base =  2 starting number =  10 current number =  31 iteration count =  2
base =  2 starting number =  12 current number =  43 iteration count =  1
base =  2 starting number =  14 current number =  23 iteration count =  1
base =  2 starting number =  15 current number =  29 iteration count =  1
base =  2 starting number =  16 current number =  20 iteration count =  1
base =  2 starting number =  16 current number =  85 iteration count =  2
base =  2 starting number =  16 current number =  177 iteration count =  3
base =  2 starting number =  16 current number =  251 iteration count =  4
base =  2 starting number =  18 current number =  46 iteration count =  1
base =  2 starting number =  18 current number =  87 iteration count =  2
base =  2 starting number =  18 current number =  125 iteration count =  3
base =  2 starting number =  18 current number =  23 iteration count =  4
base =  2 starting number =  20 current number =  85 iteration count =  1
base =  2 starting number =  20 current number =  177 iteration count =  2
base =  2 starting number =  20 current number =  251 iteration count =  3
base =  2 starting number =  21 current number =  31 iteration count =  1
base =  2 starting number =  22 current number =  43 iteration count =  1
base =  2 starting number =  24 current number =  47 iteration count =  1
base =  2 starting number =  25 current number =  22 iteration count =  1
base =  2 starting number =  25 current number =  43 iteration count =  2
base =  2 starting number =  26 current number =  45 iteration count =  1
base =  2 starting number =  26 current number =  117 iteration count =  2
base =  2 starting number =  26 current number =  237 iteration count =  3
base =  2 starting number =  26 current number =  463 iteration count =  4
base =  2 starting number =  27 current number =  15 iteration count =  1
base =  2 starting number =  27 current number =  29 iteration count =  2
base =  2 starting number =  28 current number =  87 iteration count =  1
base =  2 starting number =  28 current number =  125 iteration count =  2
base =  2 starting number =  28 current number =  23 iteration count =  3
base =  2 starting number =  30 current number =  93 iteration count =  1
base =  2 starting number =  30 current number =  127 iteration count =  2
base =  2 starting number =  32 current number =  21 iteration count =  1
base =  2 starting number =  32 current number =  31 iteration count =  2
base =  2 starting number =  33 current number =  59 iteration count =  1
base =  2 starting number =  34 current number =  81 iteration count =  1
base =  2 starting number =  34 current number =  28 iteration count =  2
base =  2 starting number =  34 current number =  87 iteration count =  3
base =  2 starting number =  34 current number =  125 iteration count =  4
base =  2 starting number =  34 current number =  23 iteration count =  5
base =  2 starting number =  35 current number =  47 iteration count =  1
base =  2 starting number =  36 current number =  174 iteration count =  1
base =  2 starting number =  36 current number =  381 iteration count =  2
base =  2 starting number =  36 current number =  511 iteration count =  3 
base =  2 starting number =  36 current number =  969 iteration count =

85
177
251
base =  2 starting number =  4 current number =  10 iteration count =  1
base =  2 starting number =  4 current number =  21 iteration count =  2
base =  2 starting number =  4 current number =  31 iteration count =  3
base =  2 starting number =  6 current number =  11 iteration count =  1
base =  2 starting number =  8 current number =  11 iteration count =  1
base =  2 starting number =  9 current number =  14 iteration count =  1
base =  2 starting number =  9 current number =  23 iteration count =  2
base =  2 starting number =  10 current number =  21 iteration count =  1
base =  2 starting number =  10 current number =  31 iteration count =  2
base =  2 starting number =  12 current number =  43 iteration count =  1
base =  2 starting number =  14 current number =  23 iteration count =  1
base =  2 starting number =  15 current number =  29 iteration count =  1
base =  2 starting number =  16 current number =  20 iteration count =  1
base =  2 starting number =  16 current number =  85 iteration count =  2
base =  2 starting number =  16 current number =  177 iteration count =  3
base =  2 starting number =  16 current number =  251 iteration count =  4
base =  2 starting number =  18 current number =  46 iteration count =  1
base =  2 starting number =  18 current number =  87 iteration count =  2
base =  2 starting number =  18 current number =  125 iteration count =  3
base =  2 starting number =  18 current number =  23 iteration count =  4
base =  2 starting number =  20 current number =  85 iteration count =  1
base =  2 starting number =  20 current number =  177 iteration count =  2
base =  2 starting number =  20 current number =  251 iteration count =  3
base =  2 starting number =  21 current number =  31 iteration count =  1
base =  2 starting number =  22 current number =  43 iteration count =  1
base =  2 starting number =  24 current number =  47 iteration count =  1
base =  2 starting number =  25 current number =  22 iteration count =  1
base =  2 starting number =  25 current number =  43 iteration count =  2
base =  2 starting number =  26 current number =  45 iteration count =  1
base =  2 starting number =  26 current number =  117 iteration count =  2
base =  2 starting number =  26 current number =  237 iteration count =  3
base =  2 starting number =  26 current number =  463 iteration count =  4
base =  2 starting number =  27 current number =  15 iteration count =  1
base =  2 starting number =  27 current number =  29 iteration count =  2
base =  2 starting number =  28 current number =  87 iteration count =  1
base =  2 starting number =  28 current number =  125 iteration count =  2
base =  2 starting number =  28 current number =  23 iteration count =  3
base =  2 starting number =  30 current number =  93 iteration count =  1
base =  2 starting number =  30 current number =  127 iteration count =  2
base =  2 starting number =  32 current number =  21 iteration count =  1
base =  2 starting number =  32 current number =  31 iteration count =  2
base =  2 starting number =  33 current number =  59 iteration count =  1
base =  2 starting number =  34 current number =  81 iteration count =  1
base =  2 starting number =  34 current number =  28 iteration count =  2
base =  2 starting number =  34 current number =  87 iteration count =  3
base =  2 starting number =  34 current number =  125 iteration count =  4
base =  2 starting number =  34 current number =  23 iteration count =  5
base =  2 starting number =  35 current number =  47 iteration count =  1
base =  2 starting number =  36 current number =  174 iteration count =  1
base =  2 starting number =  36 current number =  381 iteration count =  2
base =  2 starting number =  36 current number =  511 iteration count =  3

For $n=217$ and for $d=2$ you get as an example a cycle which is not a prime:

SageMath-Script

$$217, 255, 945, 1007, 1269,1007,1269,1007\ldots$$

Source Link

created May 14 at 18:07

mathoverflowUser

3.1k
1
9
36

Probably an interesting question is why it seems that with base $2$ instead of $10$ and the same procedure, we get large primes: (Notice that for $d=2$ the starting number $20$ gets a prime).

def ff(n,d=10):
    ll = []
    for p in sorted(prime_divisors(n)):
        dd = Integer(p).digits(d)
        dd.reverse()
        ll.extend(dd)
        if valuation(n,p)>1:
            dd = Integer(valuation(n,p)).digits(d)
            dd.reverse()
            ll.extend(dd)
    return sum(ll[len(ll)-1-i]*d**i for i in range(len(ll)))

def iter_ff(n,k,d):
    if k==0:
        return n
    else:
        return ff(iter_ff(n,k-1,d),d)

x = 2**2*5       
while not is_prime(Integer(x)):
    x = ff(x,d=2)
    print(x)    
    
maxIter = 55    
for d in range(2,11):
     for n in range(2,100):
        x = n
        i = 0
        while not is_prime(Integer(x)) and i < maxIter:
            x = ff(x,d=d)
            print("base = ",d,"starting number = ",n,"current number = ",x,"iteration count = ", i+1)
            i+=1
        #print(d,n,iter_ff(n,k,d),is_prime(Integer(iter_ff(n,k,d))))

Output:

85
177
251
base =  2 starting number =  4 current number =  10 iteration count =  1
base =  2 starting number =  4 current number =  21 iteration count =  2
base =  2 starting number =  4 current number =  31 iteration count =  3
base =  2 starting number =  6 current number =  11 iteration count =  1
base =  2 starting number =  8 current number =  11 iteration count =  1
base =  2 starting number =  9 current number =  14 iteration count =  1
base =  2 starting number =  9 current number =  23 iteration count =  2
base =  2 starting number =  10 current number =  21 iteration count =  1
base =  2 starting number =  10 current number =  31 iteration count =  2
base =  2 starting number =  12 current number =  43 iteration count =  1
base =  2 starting number =  14 current number =  23 iteration count =  1
base =  2 starting number =  15 current number =  29 iteration count =  1
base =  2 starting number =  16 current number =  20 iteration count =  1
base =  2 starting number =  16 current number =  85 iteration count =  2
base =  2 starting number =  16 current number =  177 iteration count =  3
base =  2 starting number =  16 current number =  251 iteration count =  4
base =  2 starting number =  18 current number =  46 iteration count =  1
base =  2 starting number =  18 current number =  87 iteration count =  2
base =  2 starting number =  18 current number =  125 iteration count =  3
base =  2 starting number =  18 current number =  23 iteration count =  4
base =  2 starting number =  20 current number =  85 iteration count =  1
base =  2 starting number =  20 current number =  177 iteration count =  2
base =  2 starting number =  20 current number =  251 iteration count =  3
base =  2 starting number =  21 current number =  31 iteration count =  1
base =  2 starting number =  22 current number =  43 iteration count =  1
base =  2 starting number =  24 current number =  47 iteration count =  1
base =  2 starting number =  25 current number =  22 iteration count =  1
base =  2 starting number =  25 current number =  43 iteration count =  2
base =  2 starting number =  26 current number =  45 iteration count =  1
base =  2 starting number =  26 current number =  117 iteration count =  2
base =  2 starting number =  26 current number =  237 iteration count =  3
base =  2 starting number =  26 current number =  463 iteration count =  4
base =  2 starting number =  27 current number =  15 iteration count =  1
base =  2 starting number =  27 current number =  29 iteration count =  2
base =  2 starting number =  28 current number =  87 iteration count =  1
base =  2 starting number =  28 current number =  125 iteration count =  2
base =  2 starting number =  28 current number =  23 iteration count =  3
base =  2 starting number =  30 current number =  93 iteration count =  1
base =  2 starting number =  30 current number =  127 iteration count =  2
base =  2 starting number =  32 current number =  21 iteration count =  1
base =  2 starting number =  32 current number =  31 iteration count =  2
base =  2 starting number =  33 current number =  59 iteration count =  1
base =  2 starting number =  34 current number =  81 iteration count =  1
base =  2 starting number =  34 current number =  28 iteration count =  2
base =  2 starting number =  34 current number =  87 iteration count =  3
base =  2 starting number =  34 current number =  125 iteration count =  4
base =  2 starting number =  34 current number =  23 iteration count =  5
base =  2 starting number =  35 current number =  47 iteration count =  1
base =  2 starting number =  36 current number =  174 iteration count =  1
base =  2 starting number =  36 current number =  381 iteration count =  2
base =  2 starting number =  36 current number =  511 iteration count =  3 
base =  2 starting number =  36 current number =  969 iteration count =