A309239 -id:A309239 - cp's OEIS frontend

A059975 For n > 1, a(n) is the least number of prime factors (counted with multiplicity) of any integer with n divisors; fully additive with a(p) = p-1.

0, 1, 2, 2, 4, 3, 6, 3, 4, 5, 10, 4, 12, 7, 6, 4, 16, 5, 18, 6, 8, 11, 22, 5, 8, 13, 6, 8, 28, 7, 30, 5, 12, 17, 10, 6, 36, 19, 14, 7, 40, 9, 42, 12, 8, 23, 46, 6, 12, 9, 18, 14, 52, 7, 14, 9, 20, 29, 58, 8, 60, 31, 10, 6, 16, 13, 66, 18, 24, 11, 70, 7, 72, 37, 10, 20, 16, 15, 78, 8, 8, 41

Offset: 1

Yong Kong (ykong(AT)curagen.com), Mar 05 2001

nonn

n*a(n) is the number of complex multiplications needed for the fast Fourier transform of n numbers, writing n = r1 * r2 where r1 is a prime.

This sequence with offset 1 and a(1) = 0 is completely additive with a(p^e) = e*(p-1) for prime p and e >= 0. - Werner Schulte, Feb 23 2019

			a(18) = 5 since 18 = 2*3^2, a(18) = 1*(2-1) + 2*(3-1) = 5.

Herbert S. Wilf, Algorithms and complexity, Internet Edition, Summer, 1994, p. 56.

Antti Karttunen, Table of n, a(n) for n = 1..16384 (terms 2..1000 from Vincenzo Librandi, terms 1001..10000 from Amiram Eldar)
K. V. Lever, Problem 89-11: The complexity of the standard form of an integer, SIAM Rev. 31 (3) (1989) 493-498.
Herbert S. Wilf, Algorithms and complexity, Internet Edition, 1994, p. 56.

Essentially same as A087656 apart from offset.
Cf. A000005, A138618, A309155, A309239, A327250, A341865, A373368 [= gcd(n, a(n))], A373369 [= gcd(A001414(n), a(n))].
Cf. A003159 (positions of even terms), A096268 (with offset 1, parity of terms), A373385 (positions of multiples of 3).
Leftmost column of irregular table A355029.
Other completely additive sequences with primes p mapped to a function of p include: A001222 (with a(p)=1), A001414 (with a(p)=p), A276085 (with a(p)=p#/p), A341885 (with a(p)=p*(p+1)/2), A373149 (with a(p)=prevprime(p)), A373158 (with a(p)=p#).

A059975 := proc(n)
        local a,pf,p,e ;
        a := 0 ;
        for pf in ifactors(n)[2] do
                p := op(1,pf) ;
                e := op(2,pf) ;
                a := a+e*(p-1) ;
        end do:
        a ;
end proc: # R. J. Mathar, Oct 17 2011

Table[Total[(First /@ FactorInteger[n] - 1) Last /@ FactorInteger[n]], {n, 1, 100}] (* Danny Marmer, Nov 13 2014 *)
f[p_, e_] := e*(p - 1); a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Mar 27 2023 *)

a(n) = {my(f = factor(n)); sum(i = 1, #f~, f[i, 2]*(f[i, 1] - 1));} \\ Amiram Eldar, Mar 27 2023

a(n) = Sum ( e_i * (p_i - 1) ) where n = Product ( p_i^e_i ) is the canonical factorization of n.
a(n) = min(A001222(x) : A000005(x)=n).
a(n) = row sums of A138618 - row products of A138618. - Mats Granvik, May 23 2013
a(n) = A001414(n) - A001222(n). - David James Sycamore, Jul 17 2019
a(n) = n - A341865(n). - Antti Karttunen, Jun 05 2024

Definition revised by Hugo van der Sanden, May 21 2010

Term a(1)=0 prepended and Werner Schulte's comment adopted as an alternative definition - Antti Karttunen, Jun 05 2024

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

Original entry on oeis.org

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, 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, 5, 6, 10, 9, 1, 16, 22, 9, 1, 7, 1, 37, 7, 18, 7, 11, 1, 6, 4, 41, 1, 10, 14

Offset: 1

David James Sycamore, Jul 14 2019

nonn

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.

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

Antti Karttunen, Table of n, a(n) for n = 1..65537

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

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

getk(p, n) = {my(k=1); while ((n - k) % (p - k), k++); k;}
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

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

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

More terms from Michel Marcus, Jul 16 2019

A309769 Even numbers m having at least one odd prime divisor p for which there exists a positive integer k < p-1 such that p-k|m-k.

Original entry on oeis.org

20, 28, 42, 44, 50, 52, 66, 68, 70, 76, 78, 80, 88, 92, 102, 104, 110, 112, 114, 116, 124, 130, 136, 138, 140, 148, 152, 154, 156, 164, 170, 172, 174, 176, 182, 184, 186, 188, 190, 196, 200, 204, 208, 212, 222, 228, 230, 232, 236, 238, 242, 244, 246, 248, 252

Offset: 1

David James Sycamore, Aug 16 2019

nonn

Complement in A005843 of A309239. Every odd number > 1 has the property mentioned in Name, but these are the only even numbers with this property. No term is either a power of 2 or a semiprime. A number m is a term if and only if m = 2rp, where r >= 2, and p is a prime > q, the smallest prime divisor of 2r-1 (k=p-q). For any given r, 2rz is the smallest multiple of 2r in this sequence, where z=nextprime(q). If m = 2rp is a term and 2r-1 is prime, then p is the greatest prime divisor of m (the converse is not true; e.g., m=70=10*7).

			20 = 4*5 is a term because with k=2, 5-k|20-k.
66 = 6*11 is a term (k=6), although when expressed as 66=22*3 no k exists.
110 = 10*11 = 22*5 is a term for two reasons, since with both of its odd prime factors it has the required property; 5-2|110-2 and 11-8|110-8. This is the smallest term having two distinct odd prime factors, both of which have the above property (see A309780, A309781).

Cf. A005843, A309239, A309155, A307390, A309780, A309781.

kQ[n_, p_] := Module[{ans = False}, Do[If[Divisible[n - k, p - k], ans = True; Break[]], {k, 1, p - 2}]; ans]; aQ[n_] := EvenQ[n] && Length[(p = FactorInteger[ n][[2 ;; -1, 1]])] > 0 && AnyTrue[p, kQ[n, #] &]; Select[Range[252], aQ] (* Amiram Eldar, Aug 17 2019 *)

getk(p, m) = {for (k=1, p-2, if (((m-k) % (p-k)) == 0, return(k)););}
isok(m) = {if ((m % 2) == 0, my(f = factor(m)[,1]~); if (#f == 1, return (0)); for (i=2, #f, if (getk(f[i], m), return(1));););} \\ Michel Marcus, Aug 26 2019

cp's OEIS Frontend

A059975 For n > 1, a(n) is the least number of prime factors (counted with multiplicity) of any integer with n divisors; fully additive with a(p) = p-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A309769 Even numbers m having at least one odd prime divisor p for which there exists a positive integer k < p-1 such that p-k|m-k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI