A028236 -id:A028236 - 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

A332880 If n = Product (p_j^k_j) then a(n) = numerator of Product (1 + 1/p_j).

Original entry on oeis.org

1, 3, 4, 3, 6, 2, 8, 3, 4, 9, 12, 2, 14, 12, 8, 3, 18, 2, 20, 9, 32, 18, 24, 2, 6, 21, 4, 12, 30, 12, 32, 3, 16, 27, 48, 2, 38, 30, 56, 9, 42, 16, 44, 18, 8, 36, 48, 2, 8, 9, 24, 21, 54, 2, 72, 12, 80, 45, 60, 12, 62, 48, 32, 3, 84, 24, 68, 27, 32, 72

Offset: 1

Ilya Gutkovskiy, Feb 28 2020

Numerator of sum of reciprocals of squarefree divisors of n.

(6/Pi^2) * A332881(n)/a(n) is the asymptotic density of numbers that are coprime to their digital sum in base n+1 (see A094387 and A339076 for bases 2 and 10). - Amiram Eldar, Nov 24 2022

			1, 3/2, 4/3, 3/2, 6/5, 2, 8/7, 3/2, 4/3, 9/5, 12/11, 2, 14/13, 12/7, 8/5, 3/2, 18/17, ...

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

Cf. A001615, A008683, A017665, A028235, A028236, A048250, A076512, A306695, A308443, A308462, A332881 (denominators), A332882.
Cf. also A348734, A348735.
Cf. A059956, A065463, A082020, A094387, A339076.

a:= n-> numer(mul(1+1/i[1], i=ifactors(n)[2])):
seq(a(n), n=1..80);  # Alois P. Heinz, Feb 28 2020

Table[If[n == 1, 1, Times @@ (1 + 1/#[[1]] & /@ FactorInteger[n])], {n, 1, 70}] // Numerator
Table[Sum[MoebiusMu[d]^2/d, {d, Divisors[n]}], {n, 1, 70}] // Numerator

A001615(n) = if(1==n,n, my(f=factor(n)); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1))); \\ After code in A001615
A332880(n) = numerator(A001615(n)/n);

Numerators of coefficients in expansion of Sum_{k>=1} mu(k)^2*x^k/(k*(1 - x^k)).
a(n) = numerator of Sum_{d|n} mu(d)^2/d.
a(n) = numerator of psi(n)/n.
a(p) = p + 1, where p is prime.
a(n) = A001615(n) / A306695(n) = A001615(n) / gcd(n, A001615(n)). - Antti Karttunen, Nov 15 2021
From Amiram Eldar, Nov 24 2022: (Start)
Asymptotic means:
Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k)/A332881(k) = 15/Pi^2 = 1.519817... (A082020).
Limit_{m->oo} (1/m) * Sum_{k=1..m} A332881(k)/a(k) = Product_{p prime} (1 - 1/(p*(p+1))) = 0.704442... (A065463). (End)

A066504 Sum of n/p^k over all maximal prime-power divisors of n.

Original entry on oeis.org

0, 1, 1, 1, 1, 5, 1, 1, 1, 7, 1, 7, 1, 9, 8, 1, 1, 11, 1, 9, 10, 13, 1, 11, 1, 15, 1, 11, 1, 31, 1, 1, 14, 19, 12, 13, 1, 21, 16, 13, 1, 41, 1, 15, 14, 25, 1, 19, 1, 27, 20, 17, 1, 29, 16, 15, 22, 31, 1, 47, 1, 33, 16, 1, 18, 61, 1, 21, 26, 59, 1, 17, 1, 39, 28, 23, 18, 71, 1, 21, 1, 43, 1

Offset: 1

Reinhard Zumkeller, Jan 04 2002

nonn

a(A000961(m)) = 1; a(A001358(m)) = A008472(A001358(m)).

			a(120) = 120/2^3 + 120/3^1 + 120/5^1 = 15 + 40 + 24 = 79.

R. K. Guy, Unsolved Problems in Number Theory, B8.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A005236.

Cf. A028236. - R. J. Mathar, Sep 30 2008

f[n_ ] := n*Plus @@ (1/#[[1]]^#[[2]] & /@ FactorInteger@n); Array[f, 83] (* Robert G. Wilson v *)

{ for (n=1, 1000, f=factor(n); a=sum(i=1, matsize(f)[1], n/(f[i, 1]^f[i, 2])); write("b066504.txt", n, " ", a) ) } \\ Harry J. Smith, Feb 18 2010

More terms from Robert G. Wilson v, Dec 06 2005

A332882 If n = Product (p_j^k_j) then a(n) = numerator of Product (1 + 1/p_j^k_j).

Original entry on oeis.org

1, 3, 4, 5, 6, 2, 8, 9, 10, 9, 12, 5, 14, 12, 8, 17, 18, 5, 20, 3, 32, 18, 24, 3, 26, 21, 28, 10, 30, 12, 32, 33, 16, 27, 48, 25, 38, 30, 56, 27, 42, 16, 44, 15, 4, 36, 48, 17, 50, 39, 24, 35, 54, 14, 72, 9, 80, 45, 60, 2, 62, 48, 80, 65, 84, 24, 68, 45, 32, 72

Offset: 1

Ilya Gutkovskiy, Feb 28 2020

Numerator of sum of reciprocals of unitary divisors of n.

			1, 3/2, 4/3, 5/4, 6/5, 2, 8/7, 9/8, 10/9, 9/5, 12/11, 5/3, 14/13, 12/7, 8/5, 17/16, ...

Antti Karttunen, Table of n, a(n) for n = 1..20000
Eric Weisstein's World of Mathematics, Unitary Divisor.

Cf. A017665, A028235, A028236, A034448, A077610, A306633, A319676, A323166, A332880, A332883 (denominators).

Cf. also A348734, A348735.

a:= n-> numer(mul(1+i[1]^i[2], i=ifactors(n)[2])/n):
seq(a(n), n=1..80);  # Alois P. Heinz, Feb 28 2020

Table[If[n == 1, 1, Times @@ (1 + 1/#[[1]]^#[[2]] & /@ FactorInteger[n])], {n, 1, 70}] // Numerator
Table[Sum[If[GCD[d, n/d] == 1,  1/d, 0], {d, Divisors[n]}], {n, 1, 70}] // Numerator

a(n) = numerator(sumdiv(n, d, if (gcd(d, n/d)==1, 1/d))); \\ Michel Marcus, Feb 28 2020

a(n) = numerator of Sum_{d|n, gcd(d, n/d) = 1} 1/d.
a(n) = numerator of usigma(n)/n.
a(p) = p + 1, where p is prime.
a(n) = A034448(n) / A323166(n). - Antti Karttunen, Nov 13 2021
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k)/A332883(k) = zeta(2)/zeta(3) = 1.368432... (A306633). - Amiram Eldar, Nov 21 2022

A181629 Positive integers k = p_1^{r_1} ... p_n^{r_n} such that sum_{i=1..n} p_i^{-r_i} >= 1 (Non-Hyperbolic Integers).

Original entry on oeis.org

1, 30, 210, 330, 390, 462, 510, 546, 570, 690, 714, 798, 858, 870, 930, 966, 1050, 1110, 1218, 1230, 1290, 1302, 1410, 1470, 1554, 1590, 1722, 1770, 1830, 2010, 2130, 2190, 2310, 2370, 2490, 2670, 2730, 2910, 3030, 3090, 3210, 3270, 3390, 3570, 3630, 3810

Offset: 1

Roberto E. Martinez II, Nov 02 2010, Nov 05 2010

nonn

First odd term greater than 1 is 3234846615. - Robert G. Wilson v, Nov 04 2010

Also numbers n such that A028236(n)/n >= 1. - Klaus Brockhaus, Nov 06 2010

			a(2) = 30, since 30 = 2*3*5 and 1/2 + 1/3 + 1/5 = 31/30 >= 1.

Cf. A028236 (if n = Product (p_j^k_j), a(n) = numerator of Sum 1/p_j^k_j). - Klaus Brockhaus, Nov 06 2010

[1] cat [ k: k in [2..4000] | &+[ f[i, 1]^-f[i, 2]: i in [1..#f] ] ge 1 where f is Factorization(k) ]; // Klaus Brockhaus, Nov 06 2010

DeleteCases[ Table[k; A = FactorInteger[k]; If[Sum[1/A[[j]][[1]]^A[[j]][[2]], {j, 1, Length[A]}] >= 1, k, 0], {k, 1, 3900}], 0]
fQ[n_] := Block[{fi = Transpose@ FactorInteger@ n}, Plus @@ (1/(First@fi ^ Last@fi)) >= 1]; Select[Range@ 3900, fQ] (* Robert G. Wilson v, Nov 04 2010 *)

A379141 If n = Product (p_j^k_j) then a(n) = numerator of Sum 1/k_j.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 5, 1, 2, 3, 1, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 1, 2, 1, 5, 2, 2, 2, 4, 1, 5, 2, 3, 2, 2, 2, 6, 1, 3, 3, 1, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3

Offset: 1

Ilya Gutkovskiy, Dec 16 2024

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

Cf. A001222, A005361, A028235, A028236.

a:= n-> numer(add(1/i[2], i=ifactors(n)[2])):
seq(a(n), n=1..110);  # Alois P. Heinz, Dec 16 2024

Join[{0}, Table[Plus @@ (1/#[[2]] & /@ FactorInteger[n]), {n, 2, 110}]] // Numerator

a(n) = my(f=factor(n)); numerator(sum(k=1, #f~, 1/f[k,2])); \\ Michel Marcus, Dec 16 2024

A304404 If n = Product (p_j^k_j) then a(n) = Product (n/p_j^k_j).

Original entry on oeis.org

1, 1, 1, 1, 1, 6, 1, 1, 1, 10, 1, 12, 1, 14, 15, 1, 1, 18, 1, 20, 21, 22, 1, 24, 1, 26, 1, 28, 1, 900, 1, 1, 33, 34, 35, 36, 1, 38, 39, 40, 1, 1764, 1, 44, 45, 46, 1, 48, 1, 50, 51, 52, 1, 54, 55, 56, 57, 58, 1, 3600, 1, 62, 63, 1, 65, 4356, 1, 68, 69, 4900, 1, 72, 1, 74, 75

Offset: 1

Ilya Gutkovskiy, May 12 2018

nonn

			a(60) = a(2^2*3*5) = (60/2^2) * (60/3) * (60/5) = 15 * 20 * 12 = 3600.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Ilya Gutkovskiy, Logarithmic scatter plot of a(n) up to n=30000
Index entries for sequences computed from indices in prime factorization
Index entries for sequences computed from exponents in factorization of n

Cf. A000961 (positions of ones), A001221, A003557, A007774 (fixed points), A028234, A028236, A051119, A062509, A066504, A069359, A072195, A141809, A205959, A284600, A290480.

a[n_] := Times @@ (n/#[[1]]^#[[2]] & /@ FactorInteger[n]); Table[a[n], {n, 75}]
Table[n^(PrimeNu[n] - 1), {n, 75}]

A304404(n) = (n^(omega(n)-1)); \\ Antti Karttunen, Aug 06 2018

from sympy.ntheory.factor_ import primenu
def A304404(n): return int(n**(primenu(n)-1)) # Chai Wah Wu, Jul 12 2023

a(n) = n^(omega(n)-1), where omega() = A001221.

a(n) = A062509(n)/n.

A381958 Numerator of the sum of the reciprocals of the indices of distinct prime factors of n.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 1, 1, 1, 4, 1, 3, 1, 5, 5, 1, 1, 3, 1, 4, 3, 6, 1, 3, 1, 7, 1, 5, 1, 11, 1, 1, 7, 8, 7, 3, 1, 9, 2, 4, 1, 7, 1, 6, 5, 10, 1, 3, 1, 4, 9, 7, 1, 3, 8, 5, 5, 11, 1, 11, 1, 12, 3, 1, 1, 17, 1, 8, 11, 19, 1, 3, 1, 13, 5, 9, 9, 5, 1, 4, 1, 14, 1, 7, 10, 15, 3, 6, 1, 11, 5, 10, 13, 16, 11

Offset: 1

Ilya Gutkovskiy, Mar 11 2025

			0, 1, 1/2, 1, 1/3, 3/2, 1/4, 1, 1/2, 4/3, 1/5, 3/2, 1/6, 5/4, 5/6, 1, 1/7, 3/2, 1/8, 4/3, ...

Index entries for sequences computed from indices in prime factorization

Cf. A000720, A028235, A028236, A066328, A083345, A318573, A379141, A381959 (denominators).

Join[{0}, Table[Plus @@ (1/PrimePi[#[[1]]] & /@ FactorInteger[n]), {n, 2, 95}] // Numerator]
nmax = 95; CoefficientList[Series[Sum[x^Prime[k]/(k (1 - x^Prime[k])), {k, 1, nmax}], {x, 0, nmax}], x] // Numerator // Rest

a(n) = my(f=factor(n)); numerator(sum(k=1, #f~, 1/primepi(f[k,1]))); \\ Michel Marcus, Mar 11 2025

If n = Product (p_j^k_j) then a(n) = numerator of Sum (1/pi(p_j)).

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

A365687 a(n) = number of fractions m/n, 0 <= m < n, gcd(m,n) = 1 whose partial fraction decomposition has integer part 0.

Original entry on oeis.org

1, 1, 2, 2, 4, 1, 6, 4, 6, 2, 10, 2, 12, 3, 4, 8, 16, 3, 18, 4, 6, 5, 22, 4, 20, 6, 18, 6, 28, 0, 30, 16, 10, 8, 12, 6, 36, 9, 12, 8, 40, 1, 42, 10, 12, 11, 46, 8, 42, 10, 16, 12, 52, 9, 20, 12, 18, 14, 58, 2, 60, 15, 18, 32, 24, 1, 66, 16, 22, 2, 70, 12, 72, 18, 20

Offset: 1

William P. Orrick, Sep 15 2023

nonn

If n = p_1^r_1 p_2^r_2 ... p_k^r_k where p_1, ..., p_k are distinct primes, the partial fraction decomposition of m/n has the form z + Sum_{i=1..k} a_i / p_i^r_i = z + Sum_{i=1..k} Sum_{j=1..r_i} a_ij / p_i^j where 0 < a_i < p_i^r_i, gcd(a_i,p_i) = 1, and where 0 <= a_ij < p_i (a_ij > 0 when j = r_i). z is the integer part.
If 0 < m / n < 1 and gcd(m,n) = 1 then the integer part satisfies 1 - k <= z <= 0.
If n is a nonhyperbolic number, which means that Sum_{i=1..k} 1 / p_i^r_i >= 1, then the integer part is not zero for any m/n with 0 < m / n < 1, gcd(m,n) = 1.
Assuming gcd(m,n) = 1, if m/n has integer part z then (n - m)/n has integer part 1 - k - z. This means there are equally many reduced fractions with denominator n > 1 between 0 and 1 having integer part z and integer part 1 - k - z.

			a(10) = 2 because, of the four nonnegative reduced fractions less than 1 with denominator 10, two of them (7/10 and 9/10) have integer part 0:
   1/10 = -1 + 1/2 + 3/5
   3/10 = -1 + 1/2 + 4/5
   7/10 = 1/2 + 1/5
   9/10 = 1/2 + 2/5.

Cf. A070306, A181629, A028236.

def a(n):
    b = n
    fs = factor(b)
    # bzList will hold Bezout coefficients to express 1/n as combination
    # of the reciprocals of the prime power factors of n. ppList will
    # hold the prime power factors themselves.
    bzList = []
    bz0 = 1
    ppList = []
    for f in fs:
        q = f[0]^f[1]
        ppList.append(q)
        b = b / q
        bzThis = xgcd(q,b)
        bzList.append(bz0*bzThis[2])
        bz0 = bz0 * bzThis[1]
    ct = 0
    for j in n.coprime_integers(n):
        if sum(floor(j*bzList[i]/ppList[i])\
         for i in range(len(ppList))) == 0:
            ct = ct + 1
    return(ct)

a(n) = phi(n) if n is a prime power.
a(n) = phi(n) / 2 if n is the product of powers of two distinct primes.
a(n) = 0 if n is in A181629, that is, if n is a nonhyperbolic number.
a(n) = A070306(n) if n is a prime power or a product of powers of two distinct primes.

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

A332880 If n = Product (p_j^k_j) then a(n) = numerator of Product (1 + 1/p_j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A066504 Sum of n/p^k over all maximal prime-power divisors of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A332882 If n = Product (p_j^k_j) then a(n) = numerator of Product (1 + 1/p_j^k_j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A181629 Positive integers k = p_1^{r_1} ... p_n^{r_n} such that sum_{i=1..n} p_i^{-r_i} >= 1 (Non-Hyperbolic Integers).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Mathematica

A379141 If n = Product (p_j^k_j) then a(n) = numerator of Sum 1/k_j.

Views

Author

Keywords

Links

Crossrefs

Programs