A139555 -id:A139555 - cp's OEIS frontend

A065515 Number of prime powers <= n.

1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 10, 10, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 19, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 26, 26, 27, 27, 27, 28, 28, 28, 29, 29, 29, 29, 30, 30, 31

Offset: 1

Reinhard Zumkeller, Nov 27 2001

a(n) > pi(n) = A000720(n).
From Chayim Lowen, Aug 05 2015: (Start)
a(n) <= pi(n) + A069623(n).
Conjecture: a(n) >= pi(A069623(n)) + pi(n) + 1.
Each term m is repeated A057820(m) times. (End)

			There are 9 prime powers <= 12: 1=2^0, 2, 3, 4=2^2, 5, 7, 8=2^3, 9=3^2 and 11, so a(12) = 9.

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, Chapter 4.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Prime Power

Cf. A000040, A000961, A000720, A276781 (ordinal transform).
A025528(n) = a(n) - 1.
Cf. A139555. - Reinhard Zumkeller, Oct 27 2010

a065515 n = length $ takeWhile (<= n) a000961_list
-- Reinhard Zumkeller, Apr 25 2011

N:= 100: # to get a(1) to a(N)
L:= Vector(N):
L[1]:= 1:
p:= 1:
while p < N do
  p:= nextprime(p);
  for k from 1 to floor(log[p](N)) do
    L[p^k] := 1;
  od
od:
ListTools:-PartialSums(convert(L,list)); # Robert Israel, May 03 2015

a[n_] := 1 + Count[ Range[2, n], p_ /; Length[ FactorInteger[p]] == 1]; Table[a[n], {n, 1, 73}] (* Jean-François Alcover, Oct 12 2011 *)
Accumulate[Table[If[Length[FactorInteger[n]]==1,1,0],{n,80}]] (* Harvey P. Dale, Aug 06 2016 *)
Accumulate[Table[If[PrimePowerQ[n],1,0],{n,120}]]+1 (* Harvey P. Dale, Sep 29 2016 *)

a(n)=n+=.5;1+sum(k=1,log(n)\log(2),primepi(n^(1/k))) \\ Charles R Greathouse IV, Apr 26 2012

from sympy import primepi
from sympy.ntheory.primetest import integer_nthroot
def A065515(n): return 1+sum(primepi(integer_nthroot(n,k)[0]) for k in range(1,n.bit_length())) # Chai Wah Wu, Jul 23 2024

Partial sums of A010055. - Reinhard Zumkeller, Nov 22 2009
a(n) = 1 + Sum_{k=1..log_2(n)} pi(floor(n^(1/k))). - Chayim Lowen, Aug 05 2015
a(n) = 1 + Sum_{k=2..n} floor(2*A001222(k)/(tau(k^2)-1)) where tau is A000005(n). - Anthony Browne, May 17 2016

A051250 Numbers whose reduced residue system consists of 1 and prime powers only.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60

Offset: 1

Labos Elemer

From Reinhard Zumkeller, Oct 27 2010: (Start)
Conjecture: the sequence is finite and 60 is the largest term, empirically verified up to 10^7;
A139555(a(n)) = A000010(a(n)). (End)
The sequence is indeed finite. Let pi*(x) denote the number of prime powers (including 1) up to x.  Dusart's bounds plus finite checking [up to 60184] shows that pi*(x) <= x/(log(x) - 1.1) + sqrt(x) for x >= 4.  phi(n) > n/(e^gamma log log n + 3/(log log n)) for n >= 3.  Convexity plus finite checking [up to 1096] allows a quick proof that phi(n) > pi*(n) for n > 420.  So if n > 420, the reduced residue system mod n must contain at least one number that is neither 1 nor a prime power. Hence 60 is the last term in the sequence. - Charles R Greathouse IV, Jul 14 2011

			RRS[ 60 ] = {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}.

M. Dalezman, From 30 to 60 Is Not Twice as Hard, Mathematics Magazine, Vol. 73, No. 2 (Apr. 2000), pp. 151-153.
O. Ore and N. J. Fine, Reduced Residue Systems, American Mathematical Monthly Vol. 66, No. 10 (Dec., 1959), pp. 926-927.

Cf. A048597, A048862-A048869.

Cf. A010055, A038566.

a051250 n = a051250_list !! (n-1)
a051250_list = filter (all ((== 1) . a010055) . a038566_row) [1..]
-- Reinhard Zumkeller, May 27 2015, Dec 18 2011, Oct 27 2010

fQ[n_] := Union[# == 1 || Mod[#, # - EulerPhi[#]] == 0 & /@ Select[ Range@ n, GCD[#, n] == 1 &]] == {True}; Select[ Range@ 100, fQ] (* Robert G. Wilson v, Jul 11 2011 *)

isprimepower(n)=ispower(n,,&n);isprime(n)
is(n)=for(k=2,n-1,if(gcd(n,k)==1&&!isprimepower(k),return(0)));1 \\ Charles R Greathouse IV, Jul 14 2011

A304575 a(n) = Sum_{d|n} #{k < d, k squarefree and relatively prime to d}.

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 6, 8, 7, 8, 8, 12, 9, 12, 12, 15, 12, 16, 13, 17, 16, 18, 16, 24, 17, 20, 20, 23, 18, 26, 20, 28, 23, 26, 24, 33, 24, 29, 28, 35, 27, 35, 29, 37, 34, 35, 31, 46, 32, 38, 35, 41, 33, 45, 36, 47, 38, 42, 37, 54, 38, 46, 46, 54, 42, 53, 42, 54

Offset: 1

Gus Wiseman, May 14 2018

nonn

Note that a(n) <= n.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001221, A005117, A008683, A073311, A111972, A112399, A139555, A265675, A304573, A304575, A304576.

s[n_]:=Length[Select[Range[n],And[SquareFreeQ[#],GCD[n,#]===1]&]];
Table[DivisorSum[n,s],{n,100}]

a(n) = sumdiv(n, d, #select(k->(issquarefree(k) && (gcd(k, d)==1)), [1..d])); \\ Michel Marcus, May 15 2018

a(n) = Sum_{d|n} A073311(d) (inverse Moebius transform of A073311). - Amiram Eldar, Nov 21 2024

A304574 Number of perfect powers (A001597) less than n and relatively prime to n.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 1, 3, 2, 4, 1, 4, 2, 3, 2, 5, 1, 5, 2, 4, 2, 5, 1, 5, 3, 5, 4, 7, 1, 7, 4, 6, 4, 7, 2, 9, 4, 6, 3, 9, 2, 9, 4, 5, 4, 9, 2, 9, 4, 7, 5, 10, 3, 9, 4, 7, 5, 10, 2, 10, 5, 6, 5, 10, 3, 11, 5, 8, 3, 11, 3, 11, 5, 7, 5, 10, 3, 11, 4, 8, 6, 12, 2

Offset: 1

Gus Wiseman, May 14 2018

nonn

			The a(33) = 6 perfect powers less than and relatively prime to 33 are {1, 4, 8, 16, 25, 32}.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Log log scatterplot of a(n), n = 2..2^16, showing prime n in red, proper prime powers n in gold, squarefree composite n in green, and numbers n that are neither squarefree nor prime powers in blue and purple, where purple represents powerful n that are not prime powers. Large green points highlight composite primorials n.

Cf. A000010, A000961, A001597, A005117, A007916, A073311, A139555, A304326, A304362, A304573, A304575, A304576.

Table[Length[Select[Range[n-1],And[#==1||GCD@@FactorInteger[#][[All,2]]>1,GCD[n,#]==1]&]],{n,100}] (* Corrected by Peter Luschny, May 17 2018 *)

ispow(n) = (n==1) || ispower(n);
a(n) = #select(x->(ispow(x) && (gcd(n, x) == 1)), [1..n-1]); \\ Michel Marcus, May 17 2018

def a(n):
    return len([k for k in (1..n-1) if k.is_perfect_power() and gcd(n,k) == 1])
[a(n) for n in (1..84)] # Peter Luschny, May 16 2018

a(1) = 0 corrected by Zak Seidov, May 15 2018

A304573 Number of non-perfect powers (A007916) less than n and relatively prime to n.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 4, 3, 3, 2, 6, 3, 8, 4, 5, 6, 11, 5, 13, 6, 8, 8, 17, 7, 15, 9, 13, 8, 21, 7, 23, 12, 14, 12, 17, 10, 27, 14, 18, 13, 31, 10, 33, 16, 19, 18, 37, 14, 33, 16, 25, 19, 42, 15, 31, 20, 29, 23, 48, 14, 50, 25, 30, 27, 38, 17, 55, 27, 36, 21, 59

Offset: 1

Gus Wiseman, May 14 2018

nonn

			The a(21) = 8 positive integers less than and relatively prime to 21 that are not perfect powers are {2, 5, 10, 11, 13, 17, 19, 20}.

Cf. A000005, A000010, A000961, A001597, A005117, A007916, A008683, A073311, A139555, A304326, A304362, A304574, A304575, A304576.

Table[Length[Select[Range[2,n],And[GCD@@FactorInteger[#][[All,2]]==1,GCD[n,#]==1]&]],{n,50}]

a(n) = sum(k=2, n-1, !ispower(k) && (gcd(n, k) == 1)); \\ Michel Marcus, May 15 2018

A304576 a(n) = Sum_{k < n, k squarefree and relatively prime to n} (-1)^(k-1).

Original entry on oeis.org

1, 1, 0, 2, 1, 2, 1, 4, 2, 3, 1, 4, 2, 5, 2, 7, 3, 6, 4, 7, 4, 9, 5, 8, 5, 10, 3, 9, 5, 8, 5, 13, 5, 13, 5, 11, 7, 15, 5, 14, 8, 11, 8, 17, 6, 18, 8, 15, 8, 17, 7, 19, 10, 16, 9, 20, 9, 23, 12, 15, 13, 25, 8, 26, 10, 18, 13, 26, 11, 22, 14, 22, 15, 30, 9, 29

Offset: 1

Gus Wiseman, May 14 2018

nonn

Cf. A000010, A001221, A005117, A008683, A073311, A111972, A112399, A139555, A265675, A304573, A304574, A304575.

l[n_]:=Sum[(-1)^(k-1),{k,Select[Range[n],And[SquareFreeQ[#],GCD[n,#]==1]&]}];
Table[l[n],{n,100}]

a(n) = sum(k=1, n, if (issquarefree(k) && (gcd(n,k)==1), (-1)^(k-1))); \\ Michel Marcus, May 15 2018

A139556 a(n) = sum of the prime-powers (including 1) that each are <= n and are coprime to n.

Original entry on oeis.org

1, 1, 3, 4, 10, 6, 15, 16, 27, 20, 39, 24, 50, 42, 46, 49, 79, 54, 96, 80, 96, 74, 115, 96, 133, 120, 151, 153, 190, 120, 219, 220, 232, 203, 245, 181, 282, 238, 267, 227, 319, 252, 360, 330, 334, 318, 403, 349, 443, 407, 443, 424, 499, 451, 511, 434, 494, 461

Offset: 1

Leroy Quet, Apr 27 2008

nonn

			All the positive integers <= 21 that are coprime to 21 are 1,2,4,5,8,10,11,13,16,17,19,20. Of these integers, only 1,2,4,5,8,11,13,16,17,19 are prime-powers. The sum of these prime-powers is 1+2+4+5+8+11+13+16+17+19 = 96; so a(21) = 96.

Robert Price, Table of n, a(n) for n = 1..5000

Cf. A000961, A139555.

isA000961 := proc(n) if n = 1 or isprime(n) then true; else RETURN(nops(ifactors(n)[2]) =1) ; fi ; end: A139556 := proc(n) local a,i; a := 0 ; for i from 1 to n do if isA000961(i) and gcd(i,n) = 1 then a := a+i ; fi ; od: a ; end: seq(A139556(n),n=1..100) ; # R. J. Mathar, May 12 2008

f[n_] := Plus @@ Select[Range@ n, Length@ FactorInteger@ # == 1 == GCD[n, # ] &]; Array[f, 58] (* Robert G. Wilson v *)

More terms from R. J. Mathar, May 12 2008

A382768 Number of k < n that are coprime to n and neither squarefree nor prime powers.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 3, 0, 1, 0, 5, 0, 5, 0, 2, 0, 3, 0, 6, 0, 2, 0, 7, 0, 7, 0, 2, 1, 9, 0, 9, 0, 5, 1, 12, 0, 8, 1, 7, 1, 14, 0, 15, 1, 5, 2, 10, 0, 16, 2, 8, 0, 17, 0, 18, 2, 5, 3, 16, 0, 20, 1, 10, 3, 21, 0

Offset: 1

Michael De Vlieger, Apr 04 2025

Let s = A126706, the set of numbers that are neither squarefree nor prime powers.
Let q(k) be the number of terms in A126706 that do not exceed k. For example, q(20) = 3, since s(1..3) = {12, 18, 20}.
a(n) = 0 for n < A382248(n). Only 72 numbers n are such that a(n) = 0, with n = 2310 the largest n such that a(n) = 0.
a(A002110(k)) = 0 for k < 6.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000

Cf. A002110, A073311, A126706, A139555, A382248.

nn := 120; q := 1; t := []; res := []; for n in [1..nn] do if not IsSquarefree(n) and not IsPrimePower(n) then Append(~t, n); q +:= 1; end if; c := 0; for i in [1..#t] do if GCD(t[i], n) eq 1 then c +:= 1; end if; end for; Append(~res, c); end for; res; // Vincenzo Librandi, Apr 22 2025

nn = 120; q = 1; Table[Set[{c, i}, {0, 1}]; If[Nor[SquareFreeQ[n], PrimePowerQ[n]], t[q] = n; q++]; While[i < q, If[CoprimeQ[t[i], n], c++]; i++]; c, {n, nn}]

cp's OEIS Frontend

A065515 Number of prime powers <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A051250 Numbers whose reduced residue system consists of 1 and prime powers only.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A304575 a(n) = Sum_{d|n} #{k < d, k squarefree and relatively prime to d}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A304574 Number of perfect powers (A001597) less than n and relatively prime to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Extensions

A304573 Number of non-perfect powers (A007916) less than n and relatively prime to n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

A304576 a(n) = Sum_{k < n, k squarefree and relatively prime to n} (-1)^(k-1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

A139556 a(n) = sum of the prime-powers (including 1) that each are <= n and are coprime to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions