login
For integer n with prime factors p_i (1 <= i <= r), with repetition, (Omega(n) = r); a(n) = Sum_{i=1..r} k_i, where k_i is the least positive integer such that p_i - k_i | n - k_i.
5

%I #36 Jun 13 2024 15:41:37

%S 0,1,1,2,1,3,1,3,2,5,1,4,1,7,4,4,1,5,1,4,6,11,1,5,2,13,3,6,1,7,1,5,10,

%T 17,5,6,1,19,12,7,1,5,1,10,3,23,1,6,2,5,16,12,1,7,10,9,18,29,1,8,1,31,

%U 5,6,10,9,1,16,22,9,1,7,1,37,7,18,7,11,1,6,4,41,1,10,14

%N For integer n with prime factors p_i (1 <= i <= r), with repetition, (Omega(n) = r); a(n) = Sum_{i=1..r} k_i, where k_i is the least positive integer such that p_i - k_i | n - k_i.

%C For n>1, such a k_i always exists for every p_i|n, since with k_i=p_i - 1, p-k_i =1, always divides n - p_i. omega(n)<=a(n)<=Sopf(n) - Omega(n). The left side equality applies when n is a prime or a Carmichael number. The right side equality applies to numbers n such that k_i = p_i - 1, 1 <= i <= r (it can be shown that all numbers with this property are even, see A309239). For n>2, records of a(n) occur when n is an even semiprime.

%H Antti Karttunen, <a href="/A309155/b309155.txt">Table of n, a(n) for n = 1..65537</a>

%F n a prime power p^k, (k>=1) -> a(n) = k; n an even semiprime, 2*p -> a(n) = p (because for n=2*p, k_1 = 1, and k_2 = p-1).

%F A001221(n) <= a(n) <= A001414(n) - A001222(n).

%e For n prime a(n) = 1; n = 4 = 2*2 —> k_1 = k_2 = 1, so a(4) = 1 + 1 = 2.

%t g[n_,p_] := Module[{k=1}, While[!Divisible[n - k, p - k], k++]; k]; a[1]=0; a[n_] := Module[{f = FactorInteger[n]}, p=f[[;;,1]]; e=f[[;;,2]]; Sum[e[[k]] * g[n,p[[k]]], {k, 1, Length[p]}]]; Array[a, 85] (* _Amiram Eldar_, Jul 18 2019 *)

%o (PARI) getk(p, n) = {my(k=1); while ((n - k) % (p - k), k++); k;}

%o a(n) = {my(f=factor(n)); for (i=1, #f~, f[i, 1] = getk(f[i, 1], n);); sum(i=1, #f~, f[i,1]*f[i,2]);} \\ _Michel Marcus_, Jul 16 2019

%Y Cf. A000040, A001221, A001222, A001414, A002997, A309239, A059975.

%K nonn

%O 1,4

%A _David James Sycamore_, Jul 14 2019

%E More terms from _Michel Marcus_, Jul 16 2019