A365092 Write out the canonical factorization of n and factorize the exponents in the factorization, the exponents in the factorizations of the exponents, ... until there are only prime numbers left. Replace each p in the factorization by (p-1)+1 and factorize each p-1 by the same process if p-1 > 1. Continue this process until there are only 1s left. a(n) is the number of 1s used.

0, 2, 3, 4, 5, 5, 6, 5, 5, 7, 8, 7, 8, 8, 8, 6, 7, 7, 8, 9, 9, 10, 11, 8, 7, 10, 6, 10, 11, 10, 11, 7, 11, 9, 11, 9, 10, 10, 11, 10, 11, 11, 12, 12, 10, 13, 14, 9, 8, 9, 10, 12, 13, 8, 13, 11, 11, 13, 14, 12, 13, 13, 11, 7, 13, 13, 14, 11, 14, 13, 14, 10, 11, 12, 10, 12

Offset: 1

Author

Jianing Song, Aug 21 2023

Keywords

• nonn

Comments

By definition a(2^n) = a(2) + a(n) = 2 + a(n) for all n, so every number occurs in this sequence.

Conjecture: for k >= 2, the maximum n such that a(n) = k is n = A001144(k). n = A365093(k) is the minimum such n.

Examples

			For n = 47029248, we have n = 2^10*3^8*7 = 2^(2*5)*3^(2^3)*7 = (1+1)^((1+1)*(4+1))*(2+1)^((1+1)^(2+1))*(6+1) = (1+1)^((1+1)*(2^2+1))*(2+1)^((1+1)^(2+1))*(2*3+1) = (1+1)^((1+1)*((1+1)^(1+1)+1))*(1+1+1)^((1+1)^(1+1+1))*((1+1)*(2+1)+1) = (1+1)^((1+1)*((1+1)^(1+1)+1))*(1+1+1)^((1+1)^(1+1+1))*((1+1)*(1+1+1)+1). The total number of 1s used is 23, so a(47029248) = 23.
a(1) = 0 since the prime factorization of 1 is empty.
a(2) = 2 since 2 = 1+1.
a(3) = 3 since 3 = 1+1+1.
a(4) = 4 since 4 = (1+1)^(1+1).
a(5) = 5 since 5 = (1+1)^(1+1)+1.
a(6) = 5 since 6 = (1+1)*(1+1+1).
a(7) = 6 since 7 = (1+1)*(1+1+1)+1.
a(8) = 5 since 8 = (1+1)^(1+1+1).
a(9) = 5 since 9 = (1+1+1)^(1+1).
a(10) = 7 since 10 = (1+1)*((1+1)^(1+1)+1).
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000
• StormTurbo, Using 1s to form the numbers, Bilibili video, Aug 04 2023 (in Chinese).

Crossrefs

Cf. A365093, A001144, A185102.

Programs

PARI

a(n) = if(n==2, 2, if(isprime(n), a(n-1)+1, my(f=factor(n)); sum(i=1, #f~, a(f[i,1])+a(f[i,2]))))

Python

from functools import lru_cache
from sympy import factorint, isprime
@lru_cache(maxsize=None)
def A365092(n): return n-1<<1 if n <= 2 else (sum(A365092(p)+A365092(e) for p, e in factorint(n).items()) if not isprime(n) else A365092(n-1)+1) # Chai Wah Wu, Aug 23 2023

Formula

a(2) = 2, a(p) = a(p-1)+1 for primes p > 2; a(p^e) = a(p) + a(e); a(m*n) = a(m) + a(n) for gcd(m,n) = 1.