A322382 a(n) = p*a(n/p) + 1, where p is the smallest prime divisor of n; a(1)=0.

0, 1, 1, 3, 1, 3, 1, 7, 4, 3, 1, 7, 1, 3, 4, 15, 1, 9, 1, 7, 4, 3, 1, 15, 6, 3, 13, 7, 1, 9, 1, 31, 4, 3, 6, 19, 1, 3, 4, 15, 1, 9, 1, 7, 13, 3, 1, 31, 8, 13, 4, 7, 1, 27, 6, 15, 4, 3, 1, 19, 1, 3, 13, 63, 6, 9, 1, 7, 4, 13, 1, 39, 1, 3, 19, 7, 8, 9, 1, 31, 40, 3, 1, 19, 6

Offset: 1

Author

David James Sycamore, Dec 05 2018

Keywords

• nonn

Comments

An equivalent definition of this sequence is: a(1) = 0; and for n > 1, a(n) = n*w(n), where if p1, ..., pk are the prime divisors of n (with repetition) and p1 <= p2 <= ... <= pk, then w(n) = 1/pk + 1/(pk-1*pk) + ... + 1/(p2*p3*...*pk) + ... + 1/(p1*p2*...*pk). Since 2 is smallest prime w(n) <= 1/2 + 1/(2^2) + ... + 1/(2^k), a partial sum of a series which -->1 as n-->oo. Therefore w(n) < 1 and n-a(n) is a sequence of positive numbers (1,1,2,1,4,3,6,...). For n=p^k, p a prime and n >= 1, a(n) = a(p^k) = p^(n-1) + p^(n-2) + ... + p^2 + p + 1 = (p^k-1)/(p-1); e.g., a(2^k) = 2^k - 1.

Examples

			For any prime p, a(p) = p*a(p/p)+1 = p*a(1)+1 = 1, because a(1) = 0.
For n = 6, the least prime divisor is 2, so a(6) = 2*a(6/2)+1 = 2*a(3)+1 = 3.
Using the equivalent definition we get w(6) = 1/3 + 1/6 = 1/2, so a(6) = 6*w(6) = 6*1/2 = 3. For n=32, a(32) = a(2^5) = 2^5 - 1 = 32 - 1 = 31.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16383
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Crossrefs

Cf. A000203, A003557, A006022, A020639, A032742, A322034, A322035, A052126.

Programs

Mathematica

a[n_] := #*a[n/#] + 1 &[FactorInteger[n][[1, 1]] ]; a[1] = 0; Array[a, 1000] (* Michael De Vlieger, Jun 20 2025 *)

PARI

a(n) = if (n==1, 0, my(p = vecmin(factor(n)[,1])); p*a(n/p)+1); \\ Michel Marcus, Jan 25 2019

Formula

From Antti Karttunen, Feb 28 2019 , Mar 04 2019: (Start)

a(1) = 0; for n > 1, a(n) = 1 + A020639(n)*a(A032742(n)).

If n is of the form p^k, k >= 1, then a(n) = A000203(A003557(n)). [Based on author's comments above] (End)

a(n) = Sum_{k=1..bigomega(n)} F^k(n), where F^k(n) is the k-th iterate of F(n) = A052126(n). - Ridouane Oudra, Aug 17 2024

Extensions

More terms from Michel Marcus, Jan 25 2019