A055631 -id:A055631 - cp's OEIS frontend

A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227

Offset: 1

N. J. A. Sloane

The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.
Any nonzero integer is a product of primes and units, where the units are +1 and -1. This is tied to the Fundamental Theorem of Arithmetic which proves that the factorizations are unique up to order and units. (So, since 1 = p^0 does not have a well defined prime base p, it is sometimes not regarded as a prime power. See A246655 for the sequence without 1.)
These numbers are (apart from 1) the numbers of elements in finite fields. - Franz Vrabec, Aug 11 2004
Numbers whose divisors form a geometrical progression. The divisors of p^k are 1, p, p^2, p^3, ..., p^k. - Amarnath Murthy, Jan 09 2002
These are also precisely the orders of those finite affine planes that are known to exist as of today. (The order of a finite affine plane is the number of points in an arbitrarily chosen line of that plane. This number is unique for all lines comprise the same number of points.) - Peter C. Heinig (algorithms(AT)gmx.de), Aug 09 2006
Except for first term, the index of the second number divisible by n in A002378, if the index equals n. - Mats Granvik, Nov 18 2007
These are precisely the numbers such that lcm(1,...,m-1) < lcm(1,...,m) (=A003418(m) for m>0; here for m=1, the l.h.s. is taken to be 0). We have a(n+1)=a(n)+1 if a(n) is a Mersenne prime or a(n)+1 is a Fermat prime; the converse is true except for n=7 (from Catalan's conjecture) and n=1, since 2^1-1 and 2^0+1 are not considered as Mersenne resp. Fermat prime. - M. F. Hasler, Jan 18 2007, Apr 18 2010
The sequence is A000015 without repetitions, or more formally, A000961=Union[A000015]. - Zak Seidov, Feb 06 2008
Except for a(1)=1, indices for which the cyclotomic polynomial Phi[k] yields a prime at x=1, cf. A020500. - M. F. Hasler, Apr 04 2008
Also, {A138929(k) ; k>1} = {2*A000961(k) ; k>1} = {4,6,8,10,14,16,18,22,26,32,34,38,46,50,54,58,62,64,74,82,86,94,98,...} are exactly the indices for which Phi[k](-1) is prime. - M. F. Hasler, Apr 04 2008
A143201(a(n)) = 1. - Reinhard Zumkeller, Aug 12 2008
Number of distinct primes dividing n=omega(n) < 2. - Juri-Stepan Gerasimov, Oct 30 2009
Numbers n such that Sum_{p-1|p is prime and divisor of n} = Product_{p-1|p is prime and divisor of n}. A055631(n) = A173557(n-1). - Juri-Stepan Gerasimov, Dec 09 2009, Mar 10 2010
Numbers n such that A028236(n) = 1. Klaus Brockhaus, Nov 06 2010
A188666(k) = a(k+1) for k: 2*a(k) <= k < 2*a(k+1), k > 0; notably a(n+1) = A188666(2*a(n)). - Reinhard Zumkeller, Apr 25 2011
A003415(a(n)) = A192015(n); A068346(a(n)) = A192016(n); a(n)=A192134(n) + A192015(n). - Reinhard Zumkeller, Jun 26 2011
A089233(a(n)) = 0. - Reinhard Zumkeller, Sep 04 2013
The positive integers n such that every element of the symmetric group S_n which has order n is an n-cycle. - W. Edwin Clark, Aug 05 2014
Conjecture: these are numbers m such that Sum_{k=0..m-1} k^phi(m) == phi(m) (mod m), where phi(m) = A000010(m). - Thomas Ordowski and Giovanni Resta, Jul 25 2018
Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - Michel Marcus, Jan 16 2019
Possible numbers of elements in a finite vector space. - Jianing Song, Apr 22 2021

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.
M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.
R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.
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).

T. D. Noe, 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 Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, and Tony W. H. Wong, A further investigation on covering systems with odd moduli, arXiv:2507.16135 [math.NT], 2025. See p. 3.
Brady Haran and Günter Ziegler, Cannons and Sparrows, Numberphile video (2018).
Laurentiu Panaitopol, Some of the properties of the sequence of powers of prime numbers, Rocky Mountain Journal of Mathematics, Volume 31, Number 4, Winter 2001.
Eric Weisstein's World of Mathematics, Prime Power
Eric Weisstein's World of Mathematics, Projective Plane
Index entries for "core" sequences

There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018
Cf. A008480, A010055, A065515, A095874, A025473.
Cf. indices of record values of A003418; A000668 and A019434 give a member of twin pairs a(n+1)=a(n)+1.
A138929(n) = 2*a(n).
Cf. A000040, A001221, A001477. - Juri-Stepan Gerasimov, Dec 09 2009
A028236 (if n = Product (p_j^k_j), a(n) = numerator of Sum 1/p_j^k_j). - Klaus Brockhaus, Nov 06 2010
A000015(n) = Min{term : >= n}; A031218(n) = Max{term : <= n}.
Complementary (in the positive integers) to sequence A024619. - Jason Kimberley, Nov 10 2015

import Data.Set (singleton, deleteFindMin, insert)
a000961 n = a000961_list !! (n-1)
a000961_list = 1 : g (singleton 2) (tail a000040_list) where
g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps
where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, May 01 2012, Apr 25 2011

[1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by Arkadiusz Wesolowski, Jul 20 2012

readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d,`,n) fi: od:
# second Maple program:
a:= proc(n) option remember; local k; for k from
      1+a(n-1) while nops(ifactors(k)[2])>1 do od; k
    end: a(1):=1: A000961:= a:
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 08 2013

Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]
Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]
max = 0; a = {}; Do[m = FactorInteger[n]; w = Sum[m[[k]][[1]]^m[[k]][[2]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* Artur Jasinski *)
Join[{1}, Select[Range[2, 250], PrimePowerQ]] (* Jean-François Alcover, Jul 07 2015 *)

A000961(n,l=-1,k=0)=until(n--<1,until(lA000961(lim=999,l=-1)=for(k=1,lim, l==lcm(l,k) && next; l=lcm(l,k); print1(k,",")) \\ M. F. Hasler, Jan 18 2007

isA000961(n) = (omega(n) == 1 || n == 1) \\ Michael B. Porter, Sep 23 2009

nextA000961(n)=my(m,r,p);m=2*n;for(e=1,ceil(log(n+0.01)/log(2)),r=(n+0.01)^(1/e);p=prime(primepi(r)+1);m=min(m,p^e));m \\ Michael B. Porter, Nov 02 2009

is(n)=isprimepower(n) || n==1 \\ Charles R Greathouse IV, Nov 20 2012

list(lim)=my(v=primes(primepi(lim)),u=List([1])); forprime(p=2,sqrtint(lim\1),for(e=2,log(lim+.5)\log(p),listput(u,p^e))); vecsort(concat(v,Vec(u))) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import primerange
def A000961_list(limit): # following Python style, list terms < limit
    L = [1]
    for p in primerange(1, limit):
        pe = p
        while pe < limit:
            L.append(pe)
            pe *= p
    return sorted(L) # Chai Wah Wu, Sep 08 2014, edited by M. F. Hasler, Jun 16 2022

from sympy import primepi
from sympy.ntheory.primetest import integer_nthroot
def A000961(n):
    def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Jul 23 2024

def A000961_list(n):
    R = [1]
    for i in (2..n):
        if i.is_prime_power(): R.append(i)
    return R
A000961_list(227) # Peter Luschny, Feb 07 2012

a(n) = A025473(n)^A025474(n). - David Wasserman, Feb 16 2006
a(n) = A117331(A117333(n)). - Reinhard Zumkeller, Mar 08 2006
Panaitopol (2001) gives many properties, inequalities and asymptotics, including a(n) ~ prime(n). - N. J. A. Sloane, Oct 31 2014, corrected by M. F. Hasler, Jun 12 2023 [The reference gives pi*(x) = pi(x) + pi(sqrt(x)) + ... where pi*(x) counts the terms up to x, so it is the inverse function to a(n).]
m=a(n) for some n <=> lcm(1,...,m-1) < lcm(1,...,m), where lcm(1...0):=0 as to include a(1)=1. a(n+1)=a(n)+1 <=> a(n+1)=A019434(k) or a(n)=A000668(k) for some k (by Catalan's conjecture), except for n=1 and n=7. - M. F. Hasler, Jan 18 2007, Apr 18 2010
A001221(a(n)) < 2. - Juri-Stepan Gerasimov, Oct 30 2009
A008480(a(n)) = 1 for all n >= 1. - Alois P. Heinz, May 26 2018
Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + 1 + A077761 + A136141. - François Huppé, Jul 31 2024

Description modified by Ralf Stephan, Aug 29 2014

A055632 Sum of totient function of primes dividing n is a prime.

Original entry on oeis.org

3, 6, 9, 10, 12, 14, 18, 20, 22, 24, 26, 27, 28, 30, 34, 36, 38, 40, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 66, 68, 70, 72, 74, 76, 80, 81, 82, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 112, 116, 118, 120, 122, 124, 130, 132, 134, 136, 140, 142, 144, 146

Offset: 1

Labos Elemer, Jun 06 2000

nonn

Observe that this sequence includes even numbers and for all primes p as (a phi-sum) an infinite number of solutions exist, like e.g. (2^w)*p, with 1+p-1=p Phi-sum over its factors.

			If n=2^a*3^b*5^c*7^d*11^e then prime-factor set is {2,3,5,7,11}. The totient function values of this set are {1,2,4,6,10} and the sum is 1+2+4+6+10=23.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A001221, A006093, A053571, A055631.

Select[Range@ 150, PrimeQ@ Total@ Map[EulerPhi@ # &, FactorInteger[#][[All, 1]]] &] (* Michael De Vlieger, Oct 26 2017 *)

isok(n) = my(vp = factor(n)[,1]); isprime(sum(i=1, #vp, eulerphi(vp[i]))); \\ Michel Marcus, Dec 19 2013

A055654 Difference between n and the result of "Phi-summation" over unitary divisors of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 3, 2, 0, 0, 3, 0, 0, 0, 7, 0, 4, 0, 5, 0, 0, 0, 9, 4, 0, 8, 7, 0, 0, 0, 15, 0, 0, 0, 15, 0, 0, 0, 15, 0, 0, 0, 11, 10, 0, 0, 21, 6, 8, 0, 13, 0, 16, 0, 21, 0, 0, 0, 15, 0, 0, 14, 31, 0, 0, 0, 17, 0, 0, 0, 37, 0, 0, 12, 19, 0, 0, 0, 35, 26, 0, 0, 21, 0, 0, 0, 33, 0, 20, 0, 23

Offset: 1

Labos Elemer, Jun 07 2000

Squarefree numbers are roots of a(n)=0 equation, while Min n for which a(n)=k is k^2. See also A000188, A008833.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000188, A008833, A055653, A053570, A053571, A055631, A055632, A055653, A065465.

a055654 n = a055654_list !! (n-1)
a055654_list = zipWith (-) [1..] a055653_list
-- Reinhard Zumkeller, Mar 11 2012

Table[n - DivisorSum[n, EulerPhi[#] &, CoprimeQ[#, n/#] &], {n, 92}] (* Michael De Vlieger, Oct 26 2017 *)
f[p_, e_] := p^e - p^(e-1) + 1; a[1] = 0; a[n_] := n - Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 04 2024 *)

a(n) = n - sumdiv(n, d, if (gcd(d, n/d)==1, eulerphi(d))); \\ Michel Marcus, Oct 27 2017

a(n) = {my(f = factor(n)); n - prod(k = 1, #f~, f[k,1]^f[k,2] - f[k,1]^(f[k,2] - 1) + 1);} \\ Amiram Eldar, Oct 04 2024

a(n) = n - Sum_{u|n, gcd(u,n/u) = 1} phi(u), i.e. when u is a unitary divisor of n.
a(n) = n - A055653(n). - Sean A. Irvine, Mar 30 2022
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - A065465 = 0.11848616... . - Amiram Eldar, Oct 04 2024

A174164 Numbers n such that 1 = abs(sum{p-1|p is prime and divisor of n} - product{p-1|p is prime and divisor of n}).

Original entry on oeis.org

6, 10, 12, 14, 18, 20, 22, 24, 26, 28, 30, 34, 36, 38, 40, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 68, 72, 74, 76, 80, 82, 86, 88, 90, 92, 94, 96, 98, 100, 104, 106, 108, 112, 116, 118, 120, 122, 124, 134, 136, 142, 144, 146, 148, 150, 152, 158, 160, 162, 164, 166, 172

Offset: 1

Juri-Stepan Gerasimov, Mar 10 2010

nonn

			6 is a term because 6=2*3 and 1=abs((2-1)+(3-1)-(2-1)*(3-1)).
10 is a term because 10=2*5 and 1=abs((2-1)+(5-1)-(2-1)*(5-1)).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A055631, A173557.

Union of A100367 and A143207.

From R. J. Mathar, Apr 26 2010: (Start)
A055631 := proc(n) add(d-1, d= numtheory[factorset](n) ) ; end proc:
A173557 := proc(n) mul(d-1, d= numtheory[factorset](n) ) ; end proc:
isA174164 := proc(n) A055631(n)-A173557(n) ; abs(%) = 1 ; end proc:
for n from 2 to 200 do if isA174164(n) then printf("%d,",n) ; end if; end do: (End)

filterQ[n_] := With[{pp = FactorInteger[n][[All, 1]]}, 1 == Abs[Total[pp-1] - Times @@ (pp-1)]];
Select[Range[200], filterQ] (* Jean-François Alcover, Sep 17 2020 *)

Corrected (53 replaced by 52, 90 and 120 inserted) by R. J. Mathar, Apr 26 2010

A332775 a(n) = n + sopf(n) - omega(n).

Original entry on oeis.org

1, 3, 5, 5, 9, 9, 13, 9, 11, 15, 21, 15, 25, 21, 21, 17, 33, 21, 37, 25, 29, 33, 45, 27, 29, 39, 29, 35, 57, 37, 61, 33, 45, 51, 45, 39, 73, 57, 53, 45, 81, 51, 85, 55, 51, 69, 93, 51, 55, 55, 69, 65, 105, 57, 69, 63, 77, 87, 117, 67, 121, 93, 71, 65, 81, 79, 133, 85, 93, 81, 141

Offset: 1

Wesley Ivan Hurt, Jun 08 2020

From Bernard Schott, Jun 10 2020: (Start)
All terms are odd, but not all odd integers are obtained: see A353046.
1 <= a(n) <= 2n-1 (see formula). (End)

Cf. A001221 (omega), A008472 (sopf), A010051, A055631, A353046.

Table[n - PrimeNu[n] + Sum[p, {p, Select[Divisors[n], PrimeQ]}], {n, 100}]

a(n) = n + vecsum(factor(n)[, 1]) - omega(n); \\ Michel Marcus, Jul 21 2020

a(n) = Sum_{k=1..n} k^(c(k)*(1 - ceiling(n/k) + floor(n/k))), where c is the prime characteristic (A010051).
a(n) = n + A055631(n).
From Bernard Schott, Jun 10 2020: (Start)
a(n) = 1 iff n = 1.
a(n) = 2*n-1 iff n is prime.
a(p^k) = p^k + p - 1 for p prime, k > 0. (End)

A373071 Integers k such that k-1 is a multiple of Sum_{prime|k}(prime-1).

Original entry on oeis.org

2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 65, 66, 67, 71, 73, 79, 81, 83, 89, 91, 97, 101, 103, 107, 109, 113, 120, 121, 125, 127, 128, 131, 137, 139, 149, 151, 154, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199

Offset: 1

Rafik Khalfi, May 25 2024

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Robert C. Vaughan and Kevin L. Weis, On sigma-phi numbers, Mathematika 48 (2001), 169-189.

Cf. A055631.

A246655 is a subsequence.

f:= proc(n)
 add( d-1, d= numtheory[factorset](n));
 end proc:
results := []:
for n from 2 to 1000 do  # Adjust the range as needed
 if mod(n-1, f(n)) = 0 then
 results := [op(results), n];
 end if;
end do;
results;

Select[Range[2, 200], Divisible[# - 1, Total[FactorInteger[#][[;; , 1]] - 1]] &] (* Amiram Eldar, May 26 2024 *)

isok(k) = (k>1) && (((k-1) % vecsum(apply(x->(x-1), factor(k)[,1]))) == 0); \\ Michel Marcus, May 26 2024

A174147 a(n) = n-th sum{p-1|p is prime and divisor of n} plus n-th product{p-1|p is prime and divisor of n}.

Original entry on oeis.org

0, 2, 4, 2, 8, 5, 12, 2, 4, 9, 20, 5, 24, 13, 14, 2, 32, 5, 36, 9, 20, 21, 44, 5, 8, 25, 4, 13, 56, 15, 60, 2, 32, 33, 34, 5, 72, 37, 38, 9, 80, 21, 84, 21, 14, 45, 92, 5, 12, 9, 50, 25, 104, 5, 54, 13, 56, 57, 116, 15, 120, 61, 20, 2, 64, 33, 132, 33, 68, 35, 140, 5, 144, 73, 14

Offset: 1

Juri-Stepan Gerasimov, Mar 09 2010

nonn

for n=1 sum{p-1|p is prime and divisor of 1} is zero.

Cf. A055631, A173557.

a(n)=A055631(n)+A173557(n).

Formula index corrected, a 62 replaced by 64 - R. J. Mathar, Apr 25 2010.

A333698 G.f.: Sum_{k>=1} phi(k) * x^prime(k) / (1 - x^prime(k)).

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 2, 1, 1, 3, 4, 2, 2, 3, 3, 1, 6, 2, 4, 3, 3, 5, 6, 2, 2, 3, 1, 3, 4, 4, 10, 1, 5, 7, 4, 2, 4, 5, 3, 3, 12, 4, 6, 5, 3, 7, 8, 2, 2, 3, 7, 3, 8, 2, 6, 3, 5, 5, 16, 4, 6, 11, 3, 1, 4, 6, 18, 7, 7, 5, 8, 2, 12, 5, 3, 5, 6, 4, 10, 3, 1, 13, 22, 4, 8

Offset: 1

Ilya Gutkovskiy, Apr 02 2020

nonn

			a(63) = a(3^2 * 7) = a(prime(2)^2 * prime(4)) = A000010(2) + A000010(4) = 1 + 2 = 3.

Index entries for sequences computed from indices in prime factorization

Cf. A000010, A000720, A055631, A066328, A067240.

nmax = 85; CoefficientList[Series[Sum[EulerPhi[k] x^Prime[k]/(1 - x^Prime[k]), {k, 1, nmax}], {x, 0, nmax}], x] // Rest
a[n_] := Plus @@ (EulerPhi[PrimePi[#[[1]]]] & /@ FactorInteger[n]); Table[a[n], {n, 85}]

a(n) = my(f=factor(n)); sum(k=1, #f~, eulerphi(primepi(f[k,1]))); \\ Michel Marcus, Apr 03 2020

If n = Product (p_j^k_j) then a(n) = Sum (phi(pi(p_j))).

cp's OEIS Frontend

A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Python

Sage

Formula

Extensions

A055632 Sum of totient function of primes dividing n is a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A055654 Difference between n and the result of "Phi-summation" over unitary divisors of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

A174164 Numbers n such that 1 = abs(sum{p-1|p is prime and divisor of n} - product{p-1|p is prime and divisor of n}).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A332775 a(n) = n + sopf(n) - omega(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A373071 Integers k such that k-1 is a multiple of Sum_{prime|k}(prime-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A174147 a(n) = n-th sum{p-1|p is prime and divisor of n} plus n-th product{p-1|p is prime and divisor of n}.