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,2

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.

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).

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.

Example

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).

Prog

(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

Crossrefs

Cf. A365093, A001144, A185102.

Sequence in context: A091334 A306560 A025280 * A096365 A319412 A200311

Adjacent sequences: A365089 A365090 A365091 * A365093 A365094 A365095

Keyword

nonn

Author

Jianing Song, Aug 21 2023

Status

approved