A342679 Number of steps for n to reach 1 or n by repeated application of A037916, or -1 if they are never reached.

1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 1, 2, 2, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 2, 1, 3, 1, 3, 3, 2, 1, 2, 2, 4, 2, 3, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 3, 3, 2, 3, 1, 3, 2, 3, 1, 3, 1, 2, 4, 3, 2, 3, 1, 2, 3, 2, 1, 2, 2, 2, 2, 2, 1

Offset: 2

Author

Devansh Singh, Mar 18 2021

Keywords

• nonn
• base

Comments

Let n = (p1^a1)*(p2^a2)*...*(pk^aj) be the prime-factorization of n >= 2, where primes are in ascending order and ai >= 1 for all i >= 1 and <= k, then form n' = a1 a2 a3 ... ak = A037916(n), the concatenation of the exponents. Repeat this process if n' != 1 and != n, otherwise stop.

When n is prime, a(n) = 1; when n is semiprime, a(n) = 2.

Does every n reach 1 by this process, or does there exist some n whose trajectory enters a cycle, i.e., we reach n again instead of 1?

No cycles for n <= 10^9. - Michael S. Branicky, Mar 21 2021

Examples

			3 = 3^1 -> 1, so a(3) = 1;
6 = 2^1 * 3^1 -> 11 = 11^1 -> 1, so a(6) = 2;
16 = 2^4 -> 4 = 2^2 -> 2 = 2^1 -> 1, so a(16) = 3;
50 = 2^1 * 5^2 -> 12 = 2^2 * 3^1 -> 21 = 3^1 * 7^1 -> 11 -> 1, so a(50) = 4.
		

Crossrefs

Cf. A000040, A037916.

Programs

Mathematica

Table[Length@Rest@Most@FixedPointList[FromDigits[Last/@FactorInteger@#]&,k],{k,2,100}] (* Giorgos Kalogeropoulos, Apr 01 2021 *)

PARI

f(n) = my(f=factor(n)[,2], s=""); for(i=1, #f~, s=concat(s,Str(f[i]))); eval(s); \\ A037916
a(n) = my(k=n, nb=0); while (k != 1, k = f(k); nb++); nb; \\ Michel Marcus, Mar 18 2021

Python

import sympy
N=int(input())
A342679_n=[]
for n in range(2,N+1):
    n_0=n
    steps=0
    while not sympy.isprime(n) :
        exponents=list(sympy.factorint(n).values())
        m=""
        for i in exponents:
            m=m+str(i)
        n=int(m)
        if n==n_0:
            break
        steps+=1
    A342679_n.append(steps+1)
print(A342679_n)

Python

def a(n):
  c, iter = 1, A037916(n)
  while iter != 1 and iter != n: c, iter = c+1, A037916(iter)
  return c
print([a(n) for n in range(2, 89)]) # Michael S. Branicky, Mar 20 2021