A365092 - OEIS

%I #21 Aug 24 2023 02:42:18

%S 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,

%T 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,

%U 11,13,14,12,13,13,11,7,13,13,14,11,14,13,14,10,11,12,10,12

%N 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.

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

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

%H Jianing Song, <a href="/A365092/b365092.txt">Table of n, a(n) for n = 1..10000</a>

%H StormTurbo, <a href="https://www.bilibili.com/video/BV1fP41147f5">Using 1s to form the numbers</a>, Bilibili video, Aug 04 2023 (in Chinese).

%F 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.

%e 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.

%e a(1) = 0 since the prime factorization of 1 is empty.

%e a(2) = 2 since 2 = 1+1.

%e a(3) = 3 since 3 = 1+1+1.

%e a(4) = 4 since 4 = (1+1)^(1+1).

%e a(5) = 5 since 5 = (1+1)^(1+1)+1.

%e a(6) = 5 since 6 = (1+1)*(1+1+1).

%e a(7) = 6 since 7 = (1+1)*(1+1+1)+1.

%e a(8) = 5 since 8 = (1+1)^(1+1+1).

%e a(9) = 5 since 9 = (1+1+1)^(1+1).

%e a(10) = 7 since 10 = (1+1)*((1+1)^(1+1)+1).

%o (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]))))

%o (Python)

%o from functools import lru_cache

%o from sympy import factorint, isprime

%o @lru_cache(maxsize=None)

%o 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

%Y Cf. A365093, A001144, A185102.

%K nonn

%O 1,2

%A _Jianing Song_, Aug 21 2023