A023893 -id:A023893 - cp's OEIS frontend

A085970 Number of integers ranging from 2 to n that are not prime-powers.

0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 13, 14, 15, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 23, 24, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 32, 33, 33, 34, 34, 35, 36, 36, 37, 38, 38, 39, 40, 41, 41, 42, 42, 43

Offset: 1

Reinhard Zumkeller, Jul 06 2003

nonn

For n > 2, a(n) gives the number of duplicate eliminations performed by the Sieve of Eratosthenes when sieving the interval [2, n]. - Felix Fröhlich, Dec 10 2016
Number of terms of A024619 <= n. - Felix Fröhlich, Dec 10 2016
First differs from A082997 at n = 30. - Gus Wiseman, Jul 28 2022

			The a(30) = 13 numbers: 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30. - _Gus Wiseman_, Jul 28 2022

Felix Fröhlich, Table of n, a(n) for n = 1..10000

Cf. A000720, A024619, A085972.
The complement is counted by A065515, without 1's A025528.
For primes instead of prime-powers we have A065855, with 1's A062298.
Partial sums of A143731.
The version not treating 1 as a prime-power is A356068.
A000688 counts factorizations into prime-powers.
A001222 counts prime-power divisors.
A246655 lists the prime-powers (A000961 includes 1), towers A164336.
Cf. A023893, A023894, A036234, A069513, A207375, A354911, A355743, A356064, A356065.

With[{nn = 75}, Table[n - Count[#, k_ /; k < n] - 1, {n, nn}] &@ Join[{1}, Select[Range@ nn, PrimePowerQ]]] (* Michael De Vlieger, Dec 11 2016 *)

a(n) = my(i=0); forcomposite(c=4, n, if(!isprimepower(c), i++)); i \\ Felix Fröhlich, Dec 10 2016

from sympy import primepi, integer_nthroot
def A085970(n): return n-1-sum(primepi(integer_nthroot(n,k)[0]) for k in range(1,n.bit_length())) # Chai Wah Wu, Aug 20 2024

a(n) = Max{A024619(k)<=n} k;

a(n) = n - A065515(n) = A085972(n) - A000720(n).

Name modified by Gus Wiseman, Jul 28 2022. Normally 1 is not considered a prime-power, cf. A000961, A246655.

A377054 First term of the n-th differences of the powers of primes. Inverse zero-based binomial transform of A000961.

Original entry on oeis.org

1, 1, 0, 0, 0, 1, -5, 15, -34, 63, -97, 115, -54, -251, 1184, -3536, 8736, -18993, 37009, -64545, 98442, -121393, 82008, 147432, -860818, 2710023, -7110594, 17077281, -38873146, 85085287, -179965647, 367885014, -725051280, 1372311999, -2481473550, 4257624252

Offset: 0

Gus Wiseman, Oct 22 2024

sign

			The sixth differences of A000961 begin: -5, 10, -9, 1, 6, -10, 16, -18, ..., so a(6) = -5.

The version for primes is A007442, noncomposites A030016, composites A377036.
For squarefree numbers we have A377041, nonsquarefree A377049.
This is the first column of the array A377051.
For antidiagonal-sums we have A377052, absolute A377053.
For positions of first zeros we have A377055.
A000040 lists the primes, differences A001223, seconds A036263.
A000961 lists the powers of primes, differences A057820.
A001597 lists perfect-powers, complement A007916.
A008578 lists the noncomposites, differences A075526.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
Cf. A025475, A053707, A093555, A174965, A175804, A246655, A361102, A376340, A376596, A377056.

q=Select[Range[100],#==1||PrimePowerQ[#]&];
Table[Sum[(-1)^(j-k)*Binomial[j,k]*q[[1+k]],{k,0,j}],{j,0,Length[q]/2}]

The inverse zero-based binomial transform of a sequence (q(0), q(1), q(2), ...) is the sequence p given by:

p(j) = sum_{k=0..j} (-1)^(j-k)*binomial(j,k)*q(k)

A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 6, 9, 11, 14, 16, 20, 23, 27, 31, 35, 43, 47, 55, 61, 70, 78, 88, 98, 111, 123, 136, 152, 168, 187, 204, 225, 248, 271, 296, 325, 356, 387, 418, 455, 495, 537, 581, 629, 678, 732, 787, 851, 918, 986, 1056, 1133, 1217, 1307, 1399, 1498, 1600, 1708, 1823

Offset: 0

David W. Wilson

Also number of different LCM's of partitions of n.

a(n) <= A023893(n), which counts the nonisomorphic Abelian subgroups of S_n. - M. F. Hasler, May 24 2013

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
L. Elliott, A. Levine, and J. D. Mitchell, Counting monogenic monoids and inverse monoids, arXiv:2303.12387 [math.GR], 2023.
Index entries for sequences related to lcm's

Cf. A051613 (first differences), A000792, A000793, A034891, A051625 (all cyclic subgroups), A256067.

b:= proc(n,i) option remember; local p;
      p:= `if`(i<1, 1, ithprime(i));
      `if`(n=0 or i<1, 1, b(n, i-1)+
      add(b(n-p^j, i-1), j=1..ilog[p](n)))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 15 2013

Table[ Length[ Union[ Apply[ LCM, Partitions[ n ], 1 ] ] ], {n, 30} ]
f[n_] := Length@ Union[LCM @@@ IntegerPartitions@ n]; Array[f, 60, 0]
(* Caution, the following is Extremely Slow and Resource Intensive *) CoefficientList[ Series[ Expand[ Product[1 + Sum[x^(Prime@ i^k), {k, 4}], {i, 10}]/(1 - x)], {x, 0, 30}], x]
b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0 || i<1, 1, b[n, i-1]+Sum[b[n-p^j, i-1], {j, 1, Log[p, n]}]]]; a[n_] := b[n, PrimePi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 03 2014, after Alois P. Heinz *)

/* compute David W. Wilson's g.f., needs <1 sec for 1000 terms */
N=1000;  x='x+O('x^N); /* N terms */
gf=1; /* generating function */
{ forprime(p=2,N,
    sm = 1;  pp=p;  /* sum;  prime power */
    while ( ppJoerg Arndt, Jan 19 2011 */

a(n) = Sum_{k=0..n} b(k), where b(k) is the number of partitions of k into distinct prime power parts (1 excluded) (A051613). - Vladeta Jovovic

G.f.: (Product_{p prime} (1 + Sum_{k >= 1} x^(p^k))) / (1-x). - David W. Wilson, Apr 19 2000

A322452 Number of factorizations of n into factors > 1 not including any prime powers.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 2, 1, 1, 1, 1, 0, 2, 1, 1, 1, 1, 1, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1

Offset: 1

Gus Wiseman, Dec 09 2018

nonn

Also the number of multiset partitions of the multiset of prime indices of n with no constant parts.

			The a(840) = 11 factorizations are (6*10*14), (6*140), (10*84), (12*70), (14*60), (15*56), (20*42), (21*40), (24*35), (28*30), (840).

Antti Karttunen, Table of n, a(n) for n = 1..20160
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000
Index entries for sequences computed from exponents in factorization of n

Positions of 0's are the prime powers A000961.

Cf. A000688, A001055, A001597, A023893, A023894, A050336, A064573, A294068, A321407, A321760.

acfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[acfacs[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],!PrimePowerQ[#]&]}]];
Table[Length[acfacs[n]],{n,100}]

A322452(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1)&&(d<=m)&&(1A322452(n/d, d))); (s)); \\ Antti Karttunen, Jan 03 2019

first(n) = my(res=vector(n)); for(i=1, n, f=factor(i); v=vecsort(f[,2] , , 4); f[, 2] = v; fb = factorback(f); if(fb==i, res[i] = A322452(i), res[i] = res[fb])); res \\ A322452 the function above \\ David A. Corneth, Jan 03 2019

More terms from Antti Karttunen, Jan 03 2019

A376598 Points of nonzero curvature in the sequence of prime-powers inclusive (A000961).

Original entry on oeis.org

4, 5, 7, 9, 10, 11, 12, 13, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 62, 63, 64, 65, 66, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 80

Offset: 1

Gus Wiseman, Oct 05 2024

nonn

These are points at which the second differences (A376596) are nonzero.

Inclusive means 1 is a prime-power. For the exclusive version, subtract 1 from all terms.

			The prime-powers inclusive (A000961) are:
  1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, ...
with first differences (A057820):
  1, 1, 1, 1, 2, 1, 1, 2, 2, 3, 1, 2, 4, 2, 2, 2, 2, 1, 5, 4, 2, 4, 2, 4, 6, 2, ...
with first differences (A376596):
  0, 0, 0, 1, -1, 0, 1, 0, 1, -2, 1, 2, -2, 0, 0, 0, -1, 4, -1, -2, 2, -2, 2, 2, ...
with nonzeros at (A376598):
  4, 5, 7, 9, 10, 11, 12, 13, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, ...

Gus Wiseman, Points of nonzero curvature in the prime-powers inclusive.

The first differences were A057820, see also A376340.
First differences are A376309.
These are the nonzeros of A376596 (sorted firsts A376653, exclusive A376654).
The complement is A376597.
A000961 lists prime-powers inclusive, exclusive A246655.
A001597 lists perfect-powers, complement A007916.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
`A064113 lists positions of adjacent equal prime gaps.
For prime-powers inclusive: A057820 (first differences), A376597 (second differences), A376597 (inflections and undulations), A376653 (sorted firsts in second differences).
For points of nonzero curvature: A333214 (prime), A376603 (composite), A376589 (non-perfect-power), A376592 (squarefree), A376595 (nonsquarefree), A376601 (non-prime-power).
Cf. A025475, A053707, A069623, A093555, A174965, A251092, A333254, A336416, A361102.

Join@@Position[Sign[Differences[Select[Range[1000], #==1||PrimePowerQ[#]&],2]],1|-1]

A356065 Squarefree numbers whose prime indices are all prime-powers.

Original entry on oeis.org

1, 3, 5, 7, 11, 15, 17, 19, 21, 23, 31, 33, 35, 41, 51, 53, 55, 57, 59, 67, 69, 77, 83, 85, 93, 95, 97, 103, 105, 109, 115, 119, 123, 127, 131, 133, 155, 157, 159, 161, 165, 177, 179, 187, 191, 201, 205, 209, 211, 217, 227, 231, 241, 249, 253, 255, 265, 277

Offset: 1

Gus Wiseman, Jul 25 2022

nonn

			105 has prime indices {2,3,4}, all three of which are prime-powers, so 105 is in the sequence.

The multiplicative version (factorizations) is A050361, non-strict A000688.
Heinz numbers of the partitions counted by A054685, with 1's A106244, non-strict A023894, non-strict with 1's A023893.
Counting twice-partitions of this type gives A279786, non-strict A279784.
Counting twice-factorizations gives A295935, non-strict A296131.
These are the odd products of distinct elements of A302493.
Allowing prime index 1 gives A302496, non-strict A302492.
The case of primes (instead of prime-powers) is A302590, non-strict A076610.
These are the squarefree positions of 1's in A355741.
This is the squarefree case of A355743, complement A356066.
A001222 counts prime-power divisors.
A005117 lists the squarefree numbers.
A034699 gives maximal prime-power divisor.
A246655 lists the prime-powers (A000961 includes 1), towers A164336.
A355742 chooses a prime-power divisor of each prime index.
Cf. A001970, A055887, A063834, A302601, A355731, A355744, A356064.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],SquareFreeQ[#]&&And@@PrimePowerQ/@primeMS[#]&]

Intersection of A005117 and A355743.

A377052 Antidiagonal-sums of the array A377051(n,k) = n-th term of k-th differences of powers of primes.

Original entry on oeis.org

1, 3, 4, 5, 6, 13, -6, 45, -50, 113, -98, 73, 274, -1159, 3563, -8707, 19024, -36977, 64582, -98401, 121436, -81961, -147383, 860871, -2709964, 7110655, -17077217, 38873213, -85085216, 179965720, -367884935, 725051361, -1372311916, 2481473639, -4257624155

Offset: 0

Gus Wiseman, Oct 22 2024

sign

These are the row-sums of the triangle-version of A377051.

			The sixth antidiagonal of A377051 is (8, 1, -1, -2, -3, -4, -5), so a(6) = -6.

The version for primes is A140119, noncomposites A376683, composites A377034.
For squarefree numbers we have A377039, nonsquarefree A377047.
These are the antidiagonal-sums of A377051.
The unsigned version is A377053.
For leaders we have A377054, for primes A007442 or A030016.
For first zero-positions we have A377055.
A version for partitions is A377056, cf. A175804, A053445, A281425, A320590.
A000040 lists the primes, differences A001223, seconds A036263.
A001597 lists perfect-powers, complement A007916.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
Cf. A000961, A025475, A053707, A057820, A093555, A174965, A246655, A361102, A376340, A376596, A376598.

nn=20;
t=Table[Differences[NestList[NestWhile[#+1&, #+1,!PrimePowerQ[#]&]&,1,2*nn],k],{k,0,nn}];
Total/@Table[t[[j,i-j+1]],{i,nn},{j,i}]

A321346 Number of integer partitions of n containing no prime powers > 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 5, 5, 6, 7, 8, 8, 11, 11, 14, 16, 19, 19, 25, 26, 31, 34, 40, 41, 52, 54, 63, 69, 81, 86, 105, 109, 126, 137, 160, 169, 201, 211, 242, 264, 303, 320, 375, 396, 453, 490, 557, 590, 682, 726, 823, 888, 1002, 1065, 1219

Offset: 0

Gus Wiseman, Dec 11 2018

nonn

First differs from A285798 at a(30) = 52, A285798(30) = 51.

			The a(20) = 14 integer partitions:
  (20)
  (10,10)
  (14,6)
  (18,1,1)
  (12,6,1,1)
  (6,6,6,1,1)
  (10,6,1,1,1,1)
  (15,1,1,1,1,1)
  (14,1,1,1,1,1,1)
  (12,1,1,1,1,1,1,1,1)
  (6,6,1,1,1,1,1,1,1,1)
  (10,1,1,1,1,1,1,1,1,1,1)
  (6,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
  (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350

Cf. A000607, A000961, A001597, A002095, A023893, A023894, A096258, A246655, A320322, A321347, A321378, A321665, A322452, A322454.

nn=100;
ser=Product[If[PrimePowerQ[n],1,1/(1-x^n)],{n,nn}];
CoefficientList[Series[ser,{x,0,nn}],x]

A376653 Sorted positions of first appearances in the second differences of consecutive prime-powers inclusive (A000961).

Original entry on oeis.org

1, 4, 5, 10, 12, 18, 25, 45, 47, 48, 60, 68, 69, 71, 80, 118, 121, 178, 179, 199, 206, 207, 216, 244, 245, 304, 325, 327, 402, 466, 484, 605, 801, 880, 939, 1033, 1055, 1077, 1234, 1281, 1721, 1890, 1891, 1906, 1940, 1960, 1962, 2257, 2290, 2410, 2880, 3150

Offset: 1

Gus Wiseman, Oct 06 2024

nonn

			The prime-powers inclusive (A000961) are:
  1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, ...
with first differences (A057820):
  1, 1, 1, 1, 2, 1, 1, 2, 2, 3, 1, 2, 4, 2, 2, 2, 2, 1, 5, 4, 2, 4, 2, 4, 6, 2, 3, ...
with first differences (A376596):
  0, 0, 0, 1, -1, 0, 1, 0, 1, -2, 1, 2, -2, 0, 0, 0, -1, 4, -1, -2, 2, -2, 2, 2, ...
with first appearances (A376653):
  1, 4, 5, 10, 12, 18, 25, 45, 47, 48, 60, 68, 69, 71, 80, 118, 121, 178, 179, 199, ...

For first differences we had A057820, sorted firsts A376340(n)+1 (except first term).
These are the sorted positions of first appearances in A376596.
The exclusive version is a(n) - 1 = A376654(n), except first term.
For squarefree instead of prime-power we have A376655.
A000961 lists prime-powers inclusive, exclusive A246655.
A001597 lists perfect-powers, complement A007916.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
A064113 lists positions of adjacent equal prime gaps.
For prime-powers inclusive: A057820 (first differences), A376597 (inflections and undulations), A376598 (nonzero curvature).
For second differences: A036263 (prime), A073445 (composite), A376559 (perfect-power), A376562 (non-perfect-power), A376590 (squarefree), A376593 (nonsquarefree), A376599 (non-prime-power).
Cf. A053707, A069623, A093555, A174965, A251092, A333254, A361102.

q=Differences[Select[Range[100],#==1||PrimePowerQ[#]&],2];
Select[Range[Length[q]],!MemberQ[Take[q,#-1],q[[#]]]&]

A377053 Antidiagonal-sums of the absolute value of the array A377051(n,k) = n-th term of k-th differences of powers of primes.

Original entry on oeis.org

1, 3, 4, 5, 6, 13, 24, 45, 80, 123, 174, 229, 382, 1219, 3591, 8849, 19288, 37899, 67442, 108323, 156054, 206733, 311525, 860955, 2710374, 7111657, 17080759, 38884849, 85124764, 180097856, 368321633, 726482493, 1377039690, 2496856437, 4306569569, 7016267449

Offset: 0

Gus Wiseman, Oct 22 2024

nonn

These are the row-sums of the absolute value of the triangle-version of A377051.

			The sixth antidiagonal of A377051 is (8, 1, -1, -2, -3, -4, -5), so a(6) = 24.

The version for primes is A376681, noncomposites A376684, composites A377035.
For squarefree numbers we have A377040, nonsquarefree A377048.
This is the antidiagonal-sums of the absolute value of A377051.
The signed version is A377052.
For leaders we have A377054, for primes A007442 or A030016.
For first zero-positions we have A377055.
A version for partitions is A377056, cf. A175804, A053445, A281425, A320590.
A000040 lists the primes, differences A001223, seconds A036263.
A008578 lists the noncomposites, differences A075526.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
Cf. A000961, A025475, A053707, A057820, A069623, A093555, A174965, A246655, A361102, A376340, A376596.

nn=20;
t=Table[Differences[NestList[NestWhile[#+1&, #+1,!PrimePowerQ[#]&]&,1,2*nn],k],{k,0,nn}];
Total/@Abs[Table[t[[j,i-j+1]],{i,nn},{j,i}]]

cp's OEIS Frontend

A085970 Number of integers ranging from 2 to n that are not prime-powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A377054 First term of the n-th differences of the powers of primes. Inverse zero-based binomial transform of A000961.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A009490 Number of distinct orders of permutations of n objects; number of nonisomorphic cyclic subgroups of symmetric group S_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A322452 Number of factorizations of n into factors > 1 not including any prime powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A376598 Points of nonzero curvature in the sequence of prime-powers inclusive (A000961).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A356065 Squarefree numbers whose prime indices are all prime-powers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A377052 Antidiagonal-sums of the array A377051(n,k) = n-th term of k-th differences of powers of primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A321346 Number of integer partitions of n containing no prime powers > 1.

Views

Author