A010055 -id:A010055 - cp's OEIS frontend

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

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

Offset: 1

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

A341123 Number of partitions of n into 5 prime powers (including 1).

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 9, 11, 15, 17, 23, 25, 32, 34, 42, 45, 55, 56, 68, 71, 83, 84, 100, 100, 117, 118, 136, 135, 158, 153, 179, 178, 204, 200, 234, 226, 261, 255, 291, 283, 327, 310, 357, 344, 390, 371, 430, 405, 466, 444, 505, 476, 550, 511, 589, 557, 634, 589, 684, 629

Offset: 5

Ilya Gutkovskiy, Feb 05 2021

nonn

Cf. A000961, A010055, A071330, A341112, A341122, A341124, A341125, A341126, A341127.

q:= proc(n) option remember; nops(ifactors(n)[2])<2 end:
b:= proc(n, i, t) option remember; `if`(n=0,
      `if`(t=0, 1, 0), `if`(i<1 or t<1, 0, b(n, i-1, t)+
      `if`(q(i), b(n-i, min(n-i, i), t-1), 0)))
    end:
a:= n-> b(n$2, 5):
seq(a(n), n=5..64);  # Alois P. Heinz, Feb 05 2021

q[n_] := q[n] = Length[FactorInteger[n]] < 2;
b[n_, i_, t_] := b[n, i, t] = If[n == 0,
     If[t == 0, 1, 0], If[i < 1 || t < 1, 0, b[n, i - 1, t] +
     If[q[i], b[n - i, Min[n - i, i], t - 1], 0]]];
a[n_] := b[n, n, 5];
Table[a[n], {n, 5, 64}] (* Jean-François Alcover, Feb 22 2022, after Alois P. Heinz *)

A100994 If n is a prime power p^m, m >= 1, then n, otherwise 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 1, 7, 8, 9, 1, 11, 1, 13, 1, 1, 16, 17, 1, 19, 1, 1, 1, 23, 1, 25, 1, 27, 1, 29, 1, 31, 32, 1, 1, 1, 1, 37, 1, 1, 1, 41, 1, 43, 1, 1, 1, 47, 1, 49, 1, 1, 1, 53, 1, 1, 1, 1, 1, 59, 1, 61, 1, 1, 64, 1, 1, 67, 1, 1, 1, 71, 1, 73, 1, 1, 1, 1, 1, 79, 1, 81, 1, 83, 1, 1, 1, 1, 1, 89, 1, 1

Offset: 1

Reinhard Zumkeller, Nov 26 2004

nonn

a(n) is the smallest positive integer such that n divides lcm(a(1), a(2), a(3), ..., a(n)), for all positive integers n. - Leroy Quet, May 01 2007

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A000961, A001221, A010055, A014963, A100995.

A100994[1]:=1; A100994[n_] := (n-1)*(Floor[1/PrimeNu[n]])+1; Array[A100994,100] (* Enrique Pérez Herrero, Sep 24 2011 *)
a[n_] := If[PrimePowerQ[n], n, 1];
Array[a, 100] (* Jean-François Alcover, Mar 26 2020 *)

a(n) = if (isprimepower(n), n, 1); \\ Michel Marcus, Mar 18 2018

a(n) = A014963(n)^A100995(n) = n^A010055(n);
a(A000961(n)) = A000961(n).
a(n) = 1 + (n-1)*floor(1/A001221(n)) for n > 1. - Enrique Pérez Herrero, Sep 24 2011

Definition edited to remove ambiguity by Daniel Forgues, Aug 18 2009

A223490 Smallest Fermi-Dirac factor of n.

Original entry on oeis.org

1, 2, 3, 4, 5, 2, 7, 2, 9, 2, 11, 3, 13, 2, 3, 16, 17, 2, 19, 4, 3, 2, 23, 2, 25, 2, 3, 4, 29, 2, 31, 2, 3, 2, 5, 4, 37, 2, 3, 2, 41, 2, 43, 4, 5, 2, 47, 3, 49, 2, 3, 4, 53, 2, 5, 2, 3, 2, 59, 3, 61, 2, 7, 4, 5, 2, 67, 4, 3, 2, 71, 2, 73, 2, 3, 4, 7, 2, 79

Offset: 1

Reinhard Zumkeller, Mar 20 2013

Note that this is not equal to the smallest Fermi-Dirac prime (A050376) dividing n, which is always A020639(n). - Antti Karttunen, Apr 15 2018

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
OEIS Wiki, "Fermi-Dirac representation" of n

Cf. A223491, A050376, A028233, A000040 (subsequence).
Cf. A302023, A302024, A302786, A302792.
Cf. also A020639.

Haskell
```
a223490 = head . a213925_row
```

f[p_, e_] := p^(2^IntegerExponent[e, 2]); a[n_] := Min @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 26 2020 *)

up_to = 65537;
v050376 = vector(up_to);
A050376(n) = v050376[n];
ispow2(n) = (n && !bitand(n,n-1));
i = 0; for(n=1,oo,if(ispow2(isprimepower(n)), i++; v050376[i] = n); if(i == up_to,break));
A052331(n) = { my(s=0,e); while(n > 1, fordiv(n, d, if(((n/d)>1)&&ispow2(isprimepower(n/d)), e = vecsearch(v050376, n/d); if(!e, print("v050376 too short!"); return(1/0)); s += 2^(e-1); n = d; break))); (s); };
A001511(n) = 1+valuation(n,2);
A223490(n) = if(1==n,n,A050376(A001511(A052331(n)))); \\ Antti Karttunen, Apr 15 2018

a(n) = A213925(n,1).
A209229(A100995(a(n))) = 1; A010055(a(n)) = 1.
From Antti Karttunen, Apr 15 2018: (Start)
a(1) = 1; and for n > 1, a(n) = A050376(A302786(n)).
a(n) = n / A302792(n).
a(n) = A302023(A020639(A302024(n))).
(End)

A341122 Number of partitions of n into 4 prime powers (including 1).

Original entry on oeis.org

1, 1, 2, 3, 5, 5, 8, 9, 12, 13, 17, 17, 22, 22, 26, 27, 33, 31, 39, 38, 44, 43, 51, 47, 58, 54, 63, 60, 71, 64, 79, 74, 88, 82, 99, 88, 108, 97, 116, 105, 126, 110, 134, 119, 141, 126, 153, 133, 164, 143, 172, 149, 184, 155, 194, 168, 204, 173, 215, 180, 227, 192, 238

Offset: 4

Ilya Gutkovskiy, Feb 05 2021

nonn

Cf. A000961, A010055, A071330, A341112, A341123, A341124, A341125, A341126, A341127.

q:= proc(n) option remember; nops(ifactors(n)[2])<2 end:
b:= proc(n, i, t) option remember; `if`(n=0,
      `if`(t=0, 1, 0), `if`(i<1 or t<1, 0, b(n, i-1, t)+
      `if`(q(i), b(n-i, min(n-i, i), t-1), 0)))
    end:
a:= n-> b(n$2, 4):
seq(a(n), n=4..66);  # Alois P. Heinz, Feb 05 2021

q[n_] := q[n] = Length[FactorInteger[n]] < 2;
b[n_, i_, t_] := b[n, i, t] = If[n == 0,
     If[t == 0, 1, 0], If[i < 1 || t < 1, 0, b[n, i - 1, t] +
     If[q[i], b[n - i, Min[n - i, i], t - 1], 0]]];
a[n_] := b[n, n, 4];
Table[a[n], {n, 4, 66}] (* Jean-François Alcover, Feb 22 2022, after Alois P. Heinz *)

A341124 Number of partitions of n into 6 prime powers (including 1).

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 12, 17, 20, 27, 31, 41, 45, 56, 63, 77, 83, 101, 108, 128, 136, 160, 168, 196, 204, 236, 245, 281, 288, 331, 340, 387, 395, 450, 457, 519, 525, 594, 598, 677, 678, 763, 764, 855, 851, 957, 949, 1062, 1053, 1177, 1161, 1300, 1276, 1425, 1403, 1564

Offset: 6

Ilya Gutkovskiy, Feb 05 2021

nonn

Cf. A000961, A010055, A071330, A341112, A341122, A341123, A341125, A341126, A341127.

q:= proc(n) option remember; nops(ifactors(n)[2])<2 end:
b:= proc(n, i, t) option remember; `if`(n=0,
      `if`(t=0, 1, 0), `if`(i<1 or t<1, 0, b(n, i-1, t)+
      `if`(q(i), b(n-i, min(n-i, i), t-1), 0)))
    end:
a:= n-> b(n$2, 6):
seq(a(n), n=6..62);  # Alois P. Heinz, Feb 05 2021

q[n_] := q[n] = Length[FactorInteger[n]] < 2;
b[n_, i_, t_] := b[n, i, t] = If[n == 0,
     If[t == 0, 1, 0], If[i < 1 || t < 1, 0, b[n, i - 1, t] +
     If[q[i], b[n - i, Min[n - i, i], t - 1], 0]]];
a[n_] := b[n, n, 6];
Table[a[n], {n, 6, 62}] (* Jean-François Alcover, Feb 22 2022, after Alois P. Heinz *)

A341132 Number of partitions of n into 2 distinct prime powers (including 1).

Original entry on oeis.org

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

Offset: 3

Ilya Gutkovskiy, Feb 05 2021

nonn

Cf. A000961, A010055, A071330, A282062, A306433, A307726, A341140, A341141, A341142, A341143, A341144, A341145.

q:= proc(n) option remember; nops(ifactors(n)[2])<2 end:
b:= proc(n, i, t) option remember; `if`(n=0,
      `if`(t=0, 1, 0), `if`(i<1 or t<1, 0, b(n, i-1, t)+
      `if`(q(i), b(n-i, min(n-i, i-1), t-1), 0)))
    end:
a:= n-> b(n$2, 2):
seq(a(n), n=3..90);  # Alois P. Heinz, Feb 05 2021

q[n_] := q[n] = PrimeNu[n] < 2;
b[n_, i_, t_] := b[n, i, t] = If[n == 0,
     If[t == 0, 1, 0], If[i < 1 || t < 1, 0, b[n, i - 1, t] +
     If[q[i], b[n - i, Min[n - i, i - 1], t - 1], 0]]];
a[n_] := b[n, n, 2];
Table[a[n], {n, 3, 90}] (* Jean-François Alcover, Jul 13 2021, after Alois P. Heinz *)

A139555 a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Apr 27 2008

nonn

Indices of first occurrence of each natural number: 1, 3, 5, 7, 9, 15, 11, 13, 21, 17, 19, 23, 32, 33, ..., . - Robert G. Wilson v
From Reinhard Zumkeller, Oct 27 2010: (Start)
a(n) <= A000010(n); a(A051250(n)) = A000010(A051250(n)), 1 <= n <= 17;
conjecture: a(n) < A000010(n) for n > 60, cf. A051250. (End)

			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. There are 10 of these prime-powers; so a(21) = 10.

R. Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A139556.

Cf. A065515. - Reinhard Zumkeller, Oct 27 2010

a139555 = sum . map a010055 . a038566_row
-- Reinhard Zumkeller, Feb 23 2012, Oct 27 2010

isA000961 := proc(n) if n = 1 or isprime(n) then true; else RETURN(nops(ifactors(n)[2]) =1) ; fi ; end: A139555 := 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+1 ; fi ; od: a ; end: seq(A139555(n),n=1..100) ; # R. J. Mathar, May 12 2008

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

a(n) = Sum_{k=1..A000010(n)} A010055(A038566(n,k)). - Reinhard Zumkeller, Feb 23 2012

More terms from R. J. Mathar and Robert G. Wilson v, May 12 2008

A210208 Triangle read by rows in which row n lists the divisors of n that are prime powers, A000961.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 2, 4, 1, 5, 1, 2, 3, 1, 7, 1, 2, 4, 8, 1, 3, 9, 1, 2, 5, 1, 11, 1, 2, 3, 4, 1, 13, 1, 2, 7, 1, 3, 5, 1, 2, 4, 8, 16, 1, 17, 1, 2, 3, 9, 1, 19, 1, 2, 4, 5, 1, 3, 7, 1, 2, 11, 1, 23, 1, 2, 3, 4, 8, 1, 5, 25, 1, 2, 13, 1, 3, 9, 27, 1, 2, 4, 7

Offset: 1

Reinhard Zumkeller, Mar 18 2012

{T(n,k): k = 1..A073093(n)} subset of {A027750(n,k): k = 1..A000005(n)} for all n.

			Table begins:
  1;
  1, 2;
  1, 3;
  1, 2, 4;
  1, 5;
  1, 2, 3;
  1, 7;
  1, 2, 4, 8;
  1, 3, 9;
  1, 2, 5;
  1, 11;
  1, 2, 3, 4; - _Geoffrey Critzer_, Feb 08 2015

Reinhard Zumkeller, Rows n=1..5000 of triangle, flattened
Eric Weisstein's World of Mathematics, Divisor.

Cf. A073093 (row lengths), A023888 (row sums), A034699 (row maxima), A183091 (row products).

Cf. A000005, A010055, A027750, A141809.

a210208 n k = a210208_tabf !! (n-1) !! (n-1)
a210208_row n = a210208_tabf !! (n-1)
a210208_tabf = map (filter ((== 1) . a010055)) a027750_tabf

Table[Prepend[Select[Divisors[n], PrimeNu[#] == 1 &], 1], {n, 1, 10}]//Grid (* Geoffrey Critzer, Feb 08 2015 *)

row(n) = select(x -> omega(x) < 2, divisors(n)); \\ Amiram Eldar, May 02 2025

A034699(n) = T(n,A073093(n)) = maximum of n-th row.

A341112 Number of partitions of n into 3 prime powers (including 1).

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 6, 6, 8, 8, 10, 9, 12, 10, 13, 12, 15, 13, 17, 15, 18, 15, 19, 16, 21, 17, 23, 18, 24, 19, 27, 23, 30, 24, 32, 25, 32, 26, 34, 26, 36, 26, 36, 28, 38, 28, 40, 30, 42, 32, 43, 30, 45, 32, 47, 35, 49, 30, 50, 35, 51, 36, 53, 35, 55, 37, 54, 40, 57, 36, 61, 40, 61

Offset: 3

Ilya Gutkovskiy, Feb 05 2021

nonn

Cf. A000961, A010055, A071330, A282064, A307727, A307825, A341122, A341123, A341124, A341125, A341126, A341127.

q:= proc(n) option remember; nops(ifactors(n)[2])<2 end:
b:= proc(n, i, t) option remember; `if`(n=0,
      `if`(t=0, 1, 0), `if`(i<1 or t<1, 0, b(n, i-1, t)+
      `if`(q(i), b(n-i, min(n-i, i), t-1), 0)))
    end:
a:= n-> b(n$2, 3):
seq(a(n), n=3..75);  # Alois P. Heinz, Feb 05 2021

q[n_] := q[n] = Length[FactorInteger[n]] < 2;
b[n_, i_, t_] := b[n, i, t] = If[n == 0,
     If[t == 0, 1, 0], If[i < 1 || t < 1, 0, b[n, i - 1, t] +
     If[q[i], b[n - i, Min[n - i, i], t - 1], 0]]];
a[n_] := b[n, n, 3];
Table[a[n], {n, 3, 75}] (* Jean-François Alcover, Feb 22 2022, after Alois P. Heinz *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A341123 Number of partitions of n into 5 prime powers (including 1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A100994 If n is a prime power p^m, m >= 1, then n, otherwise 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A223490 Smallest Fermi-Dirac factor of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A341122 Number of partitions of n into 4 prime powers (including 1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A341124 Number of partitions of n into 6 prime powers (including 1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A341132 Number of partitions of n into 2 distinct prime powers (including 1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A139555 a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple