A065387 -id:A065387 - cp's OEIS frontend

A001414 Integer log of n: sum of primes dividing n (with repetition). Also called sopfr(n).

0, 2, 3, 4, 5, 5, 7, 6, 6, 7, 11, 7, 13, 9, 8, 8, 17, 8, 19, 9, 10, 13, 23, 9, 10, 15, 9, 11, 29, 10, 31, 10, 14, 19, 12, 10, 37, 21, 16, 11, 41, 12, 43, 15, 11, 25, 47, 11, 14, 12, 20, 17, 53, 11, 16, 13, 22, 31, 59, 12, 61, 33, 13, 12, 18, 16, 67, 21, 26, 14, 71, 12, 73, 39, 13, 23, 18, 18

Offset: 1

N. J. A. Sloane

MacMahon calls this the potency of n.
Downgrades the operators in a prime decomposition. E.g., 40 factors as 2^3 * 5 and sopfr(40) = 2 * 3 + 5 = 11.
Consider all ways of writing n as a product of zero, one, or more factors; sequence gives smallest sum of terms. - Amarnath Murthy, Jul 07 2001
a(n) <= n for all n, and a(n) = n iff n is 4 or a prime.
Look at the graph of this sequence. At the lower edge of the logarithmic scatterplot there is a set of fuzzy but unmistakable diagonal fringes, sloping toward the southeast. Their spacing gradually increases, and their slopes gradually decrease; they are more distinct toward the lower edge of the range. Is any explanation known? - Allan C. Wechsler, Oct 11 2015
For n >= 2, the glb and lub are: 3 * log(n) / log(3) <= a(n) <= n, where the lub occurs when n = 3^k, k >= 1. (Jakimczuk 2012) - Daniel Forgues, Oct 12 2015
Except for the initial term, row sums of A027746. - M. F. Hasler, Feb 08 2016
Atanassov proves that a(n) <= A065387(n) - n. - Charles R Greathouse IV, Dec 06 2016
From Robert G. Wilson v, Aug 15 2022: (Start)
Differs from A337310 beginning with n at 64, 192, 256, 320, 448, 512, ..., .
The number of terms which equal k is A000607(k).
The first occurrence of k>1 is A056240(k).
The last occurrence of k>1 is A000792(k).
The Amarnath Murthy comment of Jul 07 2001 is a result of the fundamental theorem of arithmetic.
(End)

			a(24) = 2+2+2+3 = 9.
a(30) = 10: 30 can be written as 30, 15*2, 10*3, 6*5, 5*3*2. The corresponding sums are 30, 17, 13, 11, 10. Among these 10 is the least.

K. Atanassov, New integer functions, related to ψ and σ functions. IV., Bull. Number Theory Related Topics 12 (1988), pp. 31-35.
Amarnath Murthy, Generalization of Partition function and introducing Smarandache Factor Partition, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring-2000.
Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4.
Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 89.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from Franklin T. Adams-Watters)
Krishnaswami Alladi and Paul Erdős, On an additive arithmetic function, Pacific Journal of Mathematics, Vol. 71, No. 2 (1977), pp. 275-294, alternative link.
Kevin S. Brown, The Sum of the Prime Factors of N.
Es-said En-naoui, Study of the generalized Von Mangoldt function defined by L-additive function, arXiv:2301.09677 [math.GM], 2023.
Hans Havermann, Log plot of 100000 terms
J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis and K. Podnieks, Integer Complexity: Experimental and Analytical Results, arXiv preprint arXiv:1203.6462 [math.NT], 2012.
Rafael Jakimczuk, Sum of Prime Factors in the Prime Factorization of an Integer, International Mathematical Forum, Vol. 7, No. 53 (2012), pp. 2617-2621.
Mohan Lal, Iterates of a number-theoretic function, Math. Comp., Vol. 23, No. 105 (1969), pp. 181-183.
P. A. MacMahon, Properties of prime numbers deduced from the calculus of symmetric functions, Proc. London Math. Soc., 23 (1923), 290-316. = Coll. Papers, II, pp. 354-380.
Eric Weisstein's World of Mathematics, Sum of Prime Factors.
Wikipedia, Table of prime factors.
Steve Witham, Linear-log plot (The clear upper lines are n (the primes), n/2, n/3, n/4... but there is a dark band at sqrt(n).)
Steve Witham, Log-log plot (Differently interesting at the lower edge. Higher up, you can see sqrt(n), sqrt(n)/2, maybe sqrt(n)/3.)

Cf. A008472 (sopf(n)), A002217, A056240, A000792, A046343, A120007, A036288.
A000607(n) gives the number of values of k for which A001414(k) = n.
Cf. A036349 (indices of even terms), A356163 (their char. function), A335657 (indices of odd terms), A289142 (of multiples of 3), A373371 (their char. function).
For sum of squares of prime factors see A067666, for cubes see A224787.
Other completely additive sequences with primes p mapped to a function of p include: A001222 (with a(p)=1), A056239 (with a(p)=primepi(p)), A059975 (with a(p)=p-1), A064097 (with a(p)=1+a(p-1)), A113177 (with a(p)=Fib(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#).
For other completely additive sequences see the cross-references in A104244.

a001414 1 = 0
a001414 n = sum $ a027746_row n
-- Reinhard Zumkeller, Feb 27 2012, Nov 20 2011

[n eq 1 select 0 else (&+[j[1]*j[2]: j in Factorization(n)]): n in [1..100]]; // G. C. Greubel, Jan 10 2019

A001414 := proc(n) add( op(1,i)*op(2,i),i=ifactors(n)[2]) ; end proc:
seq(A001414(n), n=1..100); # Peter Luschny, Jan 17 2011

a[n_] := Plus @@ Times @@@ FactorInteger@ n; a[1] = 0; Array[a, 78] (* Ray Chandler, Nov 12 2005 *)

a(n)=local(f); if(n<1,0,f=factor(n); sum(k=1,matsize(f)[1],f[k,1]*f[k,2]))

A001414(n) = (n=factor(n))[,1]~*n[,2] \\ M. F. Hasler, Feb 07 2009

from sympy import factorint
def A001414(n):
    return sum(p*e for p,e in factorint(n).items()) # Chai Wah Wu, Jan 08 2016

[sum(factor(n)[j][0]*factor(n)[j][1] for j in range(0,len(factor(n)))) for n in range(1,79)] # Giuseppe Coppoletta, Jan 19 2015

If n = Product p_j^k_j then a(n) = Sum p_j * k_j.
Dirichlet g.f. f(s)*zeta(s), where f(s) = Sum_{p prime} p/(p^s-1) = Sum_{k>0} primezeta(k*s-1) is the Dirichlet g.f. for A120007. Totally additive with a(p^e) = p*e. - Franklin T. Adams-Watters, Jun 02 2006
For n > 1: a(n) = Sum_{k=1..A001222(n)} A027746(n,k). - Reinhard Zumkeller, Aug 27 2011
Sum_{n>=1} (-1)^a(n)/n^s = ((2^s + 1)/(2^s - 1))*zeta(2*s)/zeta(s), if Re(s)>1 and 0 if s=1 (Alladi and Erdős, 1977). - Amiram Eldar, Nov 02 2020
a(n) >= k*log(n), where k = 3/log(3). This bound is sharp. - Charles R Greathouse IV, Jul 28 2025

A008578 Prime numbers at the beginning of the 20th century (today 1 is no longer regarded as a prime).

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271

Offset: 1

N. J. A. Sloane

1 together with the primes; also called the noncomposite numbers.
Also largest sequence of nonnegative integers with the property that the product of 2 or more elements with different indices is never a square. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001 [Comment corrected by Farideh Firoozbakht, Aug 03 2014]
Numbers k whose largest divisor <= sqrt(k) equals 1. (See also A161344, A161345, A161424.) - Omar E. Pol, Jul 05 2009
Numbers k such that d(k) <= 2. - Juri-Stepan Gerasimov, Oct 17 2009
Also first column of array in A163280. Also first row of array in A163990. - Omar E. Pol, Oct 24 2009
Possible values of A136548(m) in increasing order, where A136548(m) = the largest numbers h such that A000203(h) <= k (k = 1,2,3,...), where A000203(h) = sum of divisors of h. - Jaroslav Krizek, Mar 01 2010
Where record values of A022404 occur: A086332(n)=A022404(a(n)). - Reinhard Zumkeller, Jun 21 2010
Positive integers that have no divisors other than 1 and itself (the old definition of prime numbers). - Omar E. Pol, Aug 10 2012
Conjecture: the sequence contains exactly those k such that sigma(k) > k*BigOmega(k). - Irina Gerasimova, Jun 08 2013
Note on the Gerasimova conjecture: all terms in the sequence obviously satisfy the inequality, because sigma(p) = 1+p and BigOmega(p) = 1 for primes p, so 1+p > p*1. For composites, the (opposite) inequality is heuristically correct at least up to k <= 4400000. The general proof requires to show that BigOmega(k) is an upper limit of the abundancy sigma(k)/k for composite k. This proof is easy for semiprimes k=p1*p2 in general, where sigma(k)=1+p1+p2+p1*p2 and BigOmega(k)=2 and p1, p2 <= 2. - R. J. Mathar, Jun 12 2013
Numbers k such that phi(k) + sigma(k) = 2k. - Farideh Firoozbakht, Aug 03 2014
isA008578(n) <=> k is prime to n for all k in {1,2,...,n-1}. - Peter Luschny, Jun 05 2017
In 1751 Leonhard Euler wrote: "Having so established this sign S to indicate the sum of the divisors of the number in front of which it is placed, it is clear that, if p indicates a prime number, the value of Sp will be 1 + p, except for the case where p = 1, because then we have S1 = 1, and not S1 = 1 + 1. From this we see that we must exclude unity from the sequence of prime numbers, so that unity, being the start of whole numbers, it is neither prime nor composite." - Omar E. Pol, Oct 12 2021
a(1) = 1; for n >= 2, a(n) is the least unused number that is coprime to all previous terms. - Jianing Song, May 28 2022
A number p is preprime if p = a*b ==> a = 1 or b = 1. This sequence lists the preprimes in the commutative monoid IN \ {0}. - Peter Luschny, Aug 26 2022

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 84 at pp. 214-217.
G. Chrystal, Algebra: An Elementary Textbook. Chelsea Publishing Company, 7th edition, (1964), chap. III.7, p. 38.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 11.
H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035
D. H. Lehmer, The sieve problem for all-purpose computers. Math. Tables and Other Aids to Computation, Math. Tables and Other Aids to Computation, 7, (1953). 6-14. Math. Rev. 14:691e
D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.
R. F. Lukes, C. D. Patterson and H. C. Williams, Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), no. 1, 113-139. Math. Rev. 96m:11082
H. C. Williams and J. O. Shallit, Factoring integers before computers. Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), 481-531, Proc. Sympos. Appl. Math., 48, AMS, Providence, RI, 1994. Math. Rev. 95m:11143

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]
Chris K. Caldwell, Angela Reddick, Yeng Xiong, and Wilfrid Keller, The History of the Primality of One: A Selection of Sources, (a dynamic survey), Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.
C. K. Caldwell and Y. Xiong, What is the smallest prime?, arXiv preprint arXiv:1209.2007 [math.HO], 2012, and J. Int. Seq. 15 (2012) #12.9.6
Leonhard Euler, Découverte d’une loi tout extraordinaire des nombres, par rapport à la somme de leurs diviseurs, in Bibliothèque impartiale, 3, 1751, pp. 10-31. Reprinted in Opera Postuma, 1, 1862, p.76-84. Number 175 in the Eneström index.
G. P. Michon, Is 1 a prime number?
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Illustration of initial terms of A008578, A161344, A161345, A161424
PrimeFan, Arguments for and against the primality of 1
A. Reddick and Y. Xiong, The search for one as a prime number: from ancient Greece to modern times, Electronic Journal of Undergraduate Mathematics, Volume 16, 1 - 13, 2012. - From _N. J. A. Sloane_, Feb 03 2013
J. Todd, Review of Lehmer's tables, Mathematical Tables and Other Aids to Computation, Vol. 11, No. 60, (1957) (on JSTOR.org).
Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]
Wikipedia, Dirichlet convolution

The main entry for this sequence is A000040.
The complement of A002808.
Cf. A000732 (boustrophedon transform).
Cf. A000010, A000203.
Cf. A023626 (self-convolution).

A008578:=Concatenation([1],Filtered([1..10^5],IsPrime)); # Muniru A Asiru, Sep 07 2017

a008578 n = a008578_list !! (n-1)
a008578_list = 1 : a000040_list
-- Reinhard Zumkeller, Nov 09 2011

[1] cat [n: n in PrimesUpTo(271)];  // Bruno Berselli, Mar 05 2011

A008578 := n->if n=1 then 1 else ithprime(n-1); fi :

Join[ {1}, Table[ Prime[n], {n, 1, 60} ] ]
NestList[ NextPrime, 1, 57] (* Robert G. Wilson v, Jul 21 2015 *)
oldPrimeQ[n_] := AllTrue[Range[n-1], CoprimeQ[#, n]&];
Select[Range[271], oldPrimeQ] (* Jean-François Alcover, Jun 07 2017, after Peter Luschny *)

PARI
```
is(n)=isprime(n)||n==1
```

isA008578 = lambda n: all(gcd(k, n) == 1 for k in (1..n-1))
print([n for n in (1..271) if isA008578(n)]) # Peter Luschny, Jun 07 2017

a(n) = A000040(n-1).
m is in the sequence iff sigma(m) + phi(m) = A065387(m) = 2m. - Farideh Firoozbakht, Jan 27 2005
a(n) = A158611(n+1) for n >= 1. - Jaroslav Krizek, Jun 19 2009
In the following formulas (based on emails from Jaroslav Krizek and R. J. Mathar), the star denotes a Dirichlet convolution between two sequences, and "This" is A008578.
This = A030014 * A008683. (Dirichlet convolution using offset 1 with A030014)
This = A030013 * A000012. (Dirichlet convolution using offset 1 with A030013)
This = A034773 * A007427. (Dirichlet convolution)
This = A034760 * A023900. (Dirichlet convolution)
This = A034762 * A046692. (Dirichlet convolution)
This * A000012 = A030014. (Dirichlet convolution using offset 1 with A030014)
This * A008683 = A030013. (Dirichlet convolution using offset 1 with A030013)
This * A000005 = A034773. (Dirichlet convolution)
This * A000010 = A034760. (Dirichlet convolution)
This * A000203 = A034762. (Dirichlet convolution)
A002033(a(n))=1. - Juri-Stepan Gerasimov, Sep 27 2009
a(n) = A181363((2*n-1)*2^k), k >= 0. - Reinhard Zumkeller, Oct 16 2010
a(n) = A001747(n)/2. - Omar E. Pol, Jan 30 2012
A060448(a(n)) = 1. - Reinhard Zumkeller, Apr 05 2012
A086971(a(n)) = 0. - Reinhard Zumkeller, Dec 14 2012
Sum_{n>=1} x^a(n) = (Sum_{n>=1} (A002815(n)*x^n))*(1-x)^2. - L. Edson Jeffery, Nov 25 2013

A051709 a(n) = sigma(n) + phi(n) - 2n.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 0, 3, 1, 2, 0, 8, 0, 2, 2, 7, 0, 9, 0, 10, 2, 2, 0, 20, 1, 2, 4, 12, 0, 20, 0, 15, 2, 2, 2, 31, 0, 2, 2, 26, 0, 24, 0, 16, 12, 2, 0, 44, 1, 13, 2, 18, 0, 30, 2, 32, 2, 2, 0, 64, 0, 2, 14, 31, 2, 32, 0, 22, 2, 28, 0, 75, 0, 2, 14, 24, 2, 36, 0

Offset: 1

Jud McCranie and Carlos Rivera

nonn

Sigma is the sum of divisors (A000203), and phi is the Euler totient function (A000010). - Michael B. Porter, Jul 05 2013
Because sigma and phi are multiplicative functions, it is easy to show that (1) if a(n)=0, then n is prime or 1 and (2) if a(n)=2, then n is the product of two distinct prime numbers. Note that a(n) is the n-th term of the Dirichlet series whose generating function is given below. Using the generating function, it is theoretically possible to compute a(n). Hence a(n)=0 could be used as a primality test and a(n)=2 could be used as a test for membership in P2 (A006881). - T. D. Noe, Aug 01 2002
It appears that a(n) - A002033(n) = zeta(s-1) * (zeta(s) - 2 + 1/zeta(s)) + 1/(zeta(s)-2). - Eric Desbiaux, Jul 04 2013
a(n) = 1 if and only if n = prime(k)^2 (n is in A001248). It seems that a(n) = k has only finitely many solutions for k >= 3. - Jianing Song, Jun 27 2021

			a(5) = sigma(5) + phi(5) - 2*5 = 6 + 4 - 10 = 0.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (First 1000 terms from T. D. Noe.)
Carlos Rivera, Puzzle 76. z(n)=sigma(n) + phi(n) - 2n, The Prime Puzzles and Problems Connection.

Cf. A000010, A000203, A001065, A001248, A005843, A006881, A051612, A051953, A065387, A072780, A228498 (= a(n^2)), A297159, A324048, A344994, A344995, A344996, A345048, A345054.
Cf. A278373 (range of this sequence), A056996 (numbers not present).
Cf. also A344753, A345001 (analogous sequences).

Table[DivisorSigma[1,n]+EulerPhi[n]-2n,{n,80}] (* Harvey P. Dale, Apr 08 2015 *)

a(n)=sigma(n)+eulerphi(n)-2*n \\ Charles R Greathouse IV, Jul 05 2013

A051709(n) = -sumdiv(n,d,(dAntti Karttunen, Mar 02 2018

Dirichlet g.f.: zeta(s-1) * (zeta(s) - 2 + 1/zeta(s)). - T. D. Noe, Aug 01 2002
From Antti Karttunen, Mar 02 2018: (Start)
a(n) = A001065(n) - A051953(n).  [Difference between the sum of proper divisors of n and their Moebius-transform.]
a(n) = -Sum_{d|n, dA008683(n/d)*A001065(d). (End)
Sum_{k=1..n} a(k) = (3/(Pi^2) + Pi^2/12 - 1) * n^2 + O(n*log(n)). - Amiram Eldar, Dec 03 2023

A038344 Numbers k such that phi(k) + sigma(k) is a prime.

Original entry on oeis.org

1, 8, 9, 32, 36, 50, 100, 225, 242, 484, 512, 578, 729, 800, 900, 1089, 1156, 1250, 1936, 2025, 2048, 2304, 2312, 2601, 2916, 3025, 3872, 4418, 6400, 7225, 7744, 8192, 8464, 8836, 9216, 10000, 12800, 14400, 20000, 20736, 21609, 26896, 27556, 31684, 32768, 33856, 34322

Offset: 1

Felice Russo

nonn

Indices k such that A065387(k) is a prime number. - R. J. Mathar, Aug 26 2009

All terms are squares or twice squares (A028982). - Donovan Johnson, Sep 27 2013

			a(2) = 8 because phi(8) + sigma(8) = 19.

Donovan Johnson, Table of n, a(n) for n = 1..1000

Cf. A000010, A000027, A000040, A000203, A028982.

[n: n in [1..40000] | IsPrime(EulerPhi(n)+DivisorSigma(1,n))]; // Vincenzo Librandi, Jul 22 2016

Select[Range[0, 40000], PrimeQ[DivisorSigma[1, #] + EulerPhi[#]] &] (* Vincenzo Librandi, Jul 22 2016 *)

isok(n) = isprime(eulerphi(n) + sigma(n)); \\ Michel Marcus, Sep 27 2013

v=vector(1000); c=0; for(j=1, 12105, m=j^2; if(isprime(eulerphi(m)+sigma(m)), c++; v[c]=m)); for(j=1, 8559, m=2*j^2; if(isprime(eulerphi(m)+sigma(m)), c++; v[c]=m)); v=vecsort(v); for(n=1, 1000, write("b038344.txt", n " " v[n])) \\ Donovan Johnson, Sep 27 2013

{k: A000203(k) + A000010(k) in A000040}. - R. J. Mathar, Aug 26 2009

More terms from Olivier Gérard

cp's OEIS Frontend

A077099 a(n) = gcd(A051612(n), A065387(n)), where A051612(n) = sigma(n) - phi(n) and A065387(n) = sigma(n) + phi(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A077100 a(n) = lcm(A051612(n), A065387(n)), where A051612(n) = sigma(n) - phi(n) and A065387(n) = sigma(n) + phi(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A077080 a(n) = phi(sigma(n) + phi(n)) = A000010(A000203(n) + A000010(n)) = A000010(A065387(n)).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

A229264 Primes in A065387 in the order of their appearance.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A077101 a(n) = A051612(n)*A065387(n) = sigma(n)^2-phi(n)^2, where A051612(n) = sigma(n) - phi(n) and A065387(n) = sigma(n) + phi(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A292768 Partial sums of A065387.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A001414 Integer log of n: sum of primes dividing n (with repetition). Also called sopfr(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI