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

A048863 Number of nonprimes (1 and composites) in the reduced residue system of n-th primorial number (A002110).

Original entry on oeis.org

1, 1, 1, 1, 6, 142, 2518, 49836, 1012859, 24211838, 721500294, 22627459401, 844130935668, 34729870646918, 1491483322755274, 69890000837179157, 3692723747920861125, 217158823263305180123, 13182405032836651359192, 879055475442725460400606

Offset: 0

Labos Elemer

			For n = 3, the 3rd primorial is 30, phi(30) = 8, a(3) = 1 since 1 is nonprime. See A048597.
For n = 4, the 4th primorial is 210, the size of its reduced residue system (RRS) is 48 of which 6 are either composite numbers or 1: {1, 121, 143, 169, 187, 209}.

Kim Walisch, Fast C++ prime counting function implementation (primecount).

Cf. A000010 (phi), A000720, A002110, A005867, A007625, A048597, A048862.

Table[Function[P, EulerPhi@ P - # &[PrimePi@ P - n]]@ Product[Prime@ i, {i, n}], {n, 0, 12}] (* Michael De Vlieger, May 08 2017 *)

a(n) = A005867(n) - A000849(n) + n.

a(n) = A000010(A002110(n)) - A000720(A002110(n)) + A001221(A002110(n)).

a(14)-a(15) from Max Alekseyev, Aug 21 2013
a(0) prepended, a(15) corrected, a(16)-a(17) computed from A000849 by Max Alekseyev, Feb 21 2016
a(18)-a(19) calculated using Kim Walisch's primecount and added by Amiram Eldar, Sep 03 2024

A286941 Irregular triangle read by rows: the n-th row corresponds to the totatives of the n-th primorial, A002110(n).

Original entry on oeis.org

1, 1, 5, 1, 7, 11, 13, 17, 19, 23, 29, 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209

Offset: 1

Jamie Morken and Michael De Vlieger, May 16 2017

Values in row n of a(n) are those of row n of A286942 complement those of row n of A279864.
From Michael De Vlieger, May 18 2017: (Start)
Numbers t < p_n# such that gcd(t, p_n#) = 0, where p_n# = A002110(n).
Numbers in the reduced residue system of A002110(n).
A005867(n) = number of terms of a(n) in row n; local minimum of Euler's totient function.
A048862(n) = number of primes in row n of a(n).
A048863(n) = number of nonprimes in row n of a(n).
Since 1 is coprime to all n, it delimits the rows of a(n).
The prime A000040(n+1) is the second term in row n since it is the smallest prime coprime to A002110(n) by definition of primorial.
The smallest composite in row n is A001248(n+1) = A000040(n+1)^2.
The Kummer numbers A057588(n) = A002110(n) - 1 are the last terms of rows n, since (n - 1) is less than and coprime to all positive n. (End)

			The triangle starts
1;
1, 5;
1, 7, 11, 13, 17, 19, 23, 29;
1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209;

Michael De Vlieger, Table of n, a(n) for n = 1..6299 (rows 1 <= n <= 6 flattened).
Mathoverflow, Lower bound for Euler's totient for almost all integers. - _Michael De Vlieger_, May 18 2017
Eric Weisstein's World of Mathematics, Totative. - _Michael De Vlieger_, May 18 2017

Cf. A002110, A005867, A048862, A057588, A279864, A286941, A286942, A309497, A038110, A058250, A329815.

Cf. A285784 (nonprimes that appear), A335334 (row sums).

Table[Function[P, Select[Range@ P, CoprimeQ[#, P] &]]@ Product[Prime@ i, {i, n}], {n, 4}] // Flatten (* Michael De Vlieger, May 18 2017 *)

row(n) = my(P=factorback(primes(n))); select(x->(gcd(x, P) == 1), [1..P]); \\ Michel Marcus, Jun 02 2020

More terms from Michael De Vlieger, May 18 2017

A285905 a(n) = A275768(A002110(n)).

Original entry on oeis.org

0, 0, 5, 26, 124, 852, 7550, 86125, 1250924, 23748764

Offset: 1

Michael De Vlieger and Jamie Morken, May 03 2017

The number of ways to express primorial p_n# = A002110(n) as (prime(i) + prime(j))/2 when (prime(i) - prime(j))/2 also is prime.
Let p_n < q <= prime(pi(p_n#)), with pi(p_n#) = A000849(n). All such primes q are coprime to primorial p_n# since they are larger than the greatest prime factor of p_n#. One of the two primes counted by a(n) must be a prime q, the other a prime r = (2p_n# - q). Further, (r - q) must be prime to be counted by a(n). Therefore an efficient method of computing a(n) begins with generating the range of prime totatives prime(n + 1) <= q <= prime(pi(p_n#)) of primorial p_n#, the number of which is given by A048862(n).
a(n) < A048862(n) < A000849(n) for n > 2.

			a(3) = 5 since there are 5 ways to express A002110(3) = 30 as (prime(i) + prime(j))/2 with (prime(i) - prime(j))/2 also prime:
  (53 + 7)/2 = 30, (53 - 7)/2 = 46/2 = 23
  (47 + 13)/2 = 30, (47 - 13)/2 = 34/2 = 17
  (43 + 17)/2 = 30, (43 - 17)/2 = 26/2 = 13
  (41 + 19)/2 = 30, (41 - 19)/2 = 22/2 = 11
  (37 + 23)/2 = 30, (37 - 23)/2 = 14/2 = 7.

Eric Weisstein's World of Mathematics, Primorial
Eric Weisstein's World of Mathematics, Totative

Cf. A000849, A002110, A048862, A275768.

With[{j = 10^3}, Do[Module[{P = Times @@ Prime@ Range@ n, m}, m = PrimePi@ P; Print@ Total@ Reap[Do[Sow@ Count[Map[{2 P - #, #} &, Prime@ Range[Max[n, k], Min[k + j - 1, m]]], w_ /; And[PrimeQ@ First@ w, PrimeQ[(Subtract @@ w)/2]]], {k, 1, m, j}]][[-1, 1]]], {n, 9}]] (* or *)
Table[Function[P, Count[Map[{2 P - #, #} &, #], w_ /; And[PrimeQ@ First@ w, PrimeQ[(Subtract @@ w)/2]]] &@ Flatten@ Select[Prime@ Range[n + 1, PrimePi[P]], Times @@ Boole@ Map[PrimeQ, {#, P - #}] == 1 &]]@ Product[Prime@ i, {i, n}], {n, 9}] (* Michael De Vlieger, May 03 2017 *)
countOfPrimes = 0
countOfPrimes2 = 0
countOfPrimes3 = 0
Pn10 = 2*3*5*7*11*13*17*19*23*29
PnToUse = Pn10
distanceToCheck = PnToUse
For[i=0,iJamie Morken, May 05 2017 *)

A048980 Difference between number of nonprimes and primes in reduced residue system of primorial numbers.

Original entry on oeis.org

1, 1, 0, -6, -36, -196, -724, 7512, 366838, 11928316, 421130508, 14598816402, 584642184936, 25314953837836, 1128885572358548, 54492272309366314, 2950485568862138250, 213151926413154110951

Offset: 0

Labos Elemer

sign

			n=4, Q(4)=2*3*5*7=210, reduced residue system includes 48 terms:42 primes and 6 composites and 1: a(4)=6-42=-36.

Cf. A048868, A048867, A048597, A002110, A048862, A048863, A048866.

Table[Function[P, EulerPhi@ P - 2 # &[PrimePi@ P - n]]@ Product[Prime@ i, {i, n}], {n, 0, 12}] (* Michael De Vlieger, May 08 2017 *)

a(n) = A048863(n) - A048862(n) = A048866(A002110(n)).

a(n) = A005867(n) - 2*A000849(n) + 2*n.

Corrected and extended by Max Alekseyev, Feb 22 2016

A048982 Number of numbers which have a "prime-rich" reduced residue system (RRS) and binary order n.

Original entry on oeis.org

0, 0, 0, 1, 3, 8, 15, 22, 32, 50, 85, 80, 98, 84, 59, 37, 10, 2, 0, 0, 0

Offset: 0

Labos Elemer

It is remarkable that in exponentially increasing ranges these occurrences increase to n=13 and thereafter decline to zero. So A048868 is believed to be finite.

			In binary order (A029837) zone of 7, i.e., in [65,128], 22 numbers belong to A048868: 66, 68, 70, 72, 74, 76, 78, 80, 84, 88, 90, 96, 98, 100, 102, 104, 108, 110, 112, 114, 120, and 126. The largest term is 90090. The largest 4 are divisible by 2310, the largest 28 by 210, and the largest 103 by 30.

Cf. A048862, A048863, A048864, A048865, A048866, A048867, A048868, A048869.

Cf. A002110, A029837, A048597.

A276497 Number of noncomposites in the reduced residue system of n-th primorial number, A002110(n).

Original entry on oeis.org

1, 2, 8, 43, 339, 3243, 42325, 646022, 12283523, 300369787, 8028643000, 25948875073, 9414916809083, 362597750396727, 15397728527812844, 742238179058722876, 40068968501510691878

Offset: 1

Andres Cicuttin, Sep 29 2016

Cf. A000849, A002110, A048862.

Primorial[n_] := Product[Prime[j], {j, 1, n}];
Table[PrimePi[Primorial[n]] - n + 1, {n, 1, 12}]

a(n) = primepi(prod(k=1,n,prime(k))) - n + 1; \\ Michel Marcus, Oct 03 2016

a(n) = pi(primorial(n)) - n + 1, n > 0.
a(n) = A000849(n) - n + 1, n > 0.
a(n) = A048862(n) + 1. - Michel Marcus, Oct 03 2016

Definition aligned with formulas and data by Peter Munn, Sep 06 2023

A286424 Number of partitions of p_n# into parts (q, k) both coprime to p_n#, with q prime and k nonprime, where p_n# = A002110(n).

Original entry on oeis.org

0, 0, 1, 1, 4, 110, 1432, 23338, 397661, 8193828, 212858328, 5941706227

Offset: 0

Michael De Vlieger, May 08 2017

Number of totative pairs (q, k) such that prime q + k nonprime = p_n# and both gcd(q, p_n#) = 1 and gcd(k, p_n#) = 1, with p_n < q <= pi(p_n#), where pi(p_n#) = A000849(n) - n = A048862(n).
Primes p_n < q <= pi(p_n#) are greater than the greatest prime factor of p_n# = p_n, and are thus coprime to p_n#. By the definition of primorial, we need not consider p >= p_n, as these p are divisors of p_n#, i.e., gcd(p, p_n#) = p. Since the totatives of m can be paired such that a + b = m, we need only determine if (p_n# - q) is not prime in order to count pairs (q, k).
a(n) < floor(A005867(n)/2).
a(n) <= A048862(n).
The totative pair (q,1) = (p_n# - 1, 1) is counted by a(n) for n in A057704, with (p_n# - 1) appearing in A057705.

			a(0) = 0 by definition. A002110(0) = 1; 1 is coprime to all numbers; the only possible totative pair is (1,1) and this does not include both a prime and a nonprime.
a(1) = 0 since, of the floor(A005867(1)/2) = 1 totative pair (1,1) of A002110(1) = 2, none include a both a prime and a nonprime.
a(2) = 1 since, the only totative pair (1,5) of A002110(1) = 6 includes both a prime and a nonprime.
a(3) = 1 since only (1,29) includes both a prime and a nonprime.
a(4) = 4 since (23,187), (41,169), (67,143), (89,121) include a both a prime and a nonprime.

C. K. Caldwell, The Prime Glossary, Primorial.
Eric Weisstein's World of Mathematics, Totative.

Cf. A000849, A002110, A005867, A048862, A048863, A057704, A057705, A116979, A117929.

Table[Function[P, Count[Prime@ Range[n + 1, PrimePi[P]], q_ /; ! PrimeQ[P - q]]]@ Product[Prime@ i, {i, n}], {n, 0, 9}] (* Michael De Vlieger, May 08 2017 *)

a(n) = (A000010(A002110(n)) - A048863(n)) - 2*A117929(A002110(n))
     = (A005867(n) - A048863(n)) - 2*A117929(A002110(n))
     = A048862(n) - 2*A117929(A002110(n)).

a(11) from Giovanni Resta, May 09 2017

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

A048863 Number of nonprimes (1 and composites) in the reduced residue system of n-th primorial number (A002110).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A286941 Irregular triangle read by rows: the n-th row corresponds to the totatives of the n-th primorial, A002110(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A285905 a(n) = A275768(A002110(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A048980 Difference between number of nonprimes and primes in reduced residue system of primorial numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A048982 Number of numbers which have a "prime-rich" reduced residue system (RRS) and binary order n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A276497 Number of noncomposites in the reduced residue system of n-th primorial number, A002110(n).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A286424 Number of partitions of p_n# into parts (q, k) both coprime to p_n#, with q prime and k nonprime, where p_n# = A002110(n).

Views

Author

Keywords

Comments

Examples

Links