A060679 -id:A060679 - cp's OEIS frontend

A070309 Number of solutions 2<=x<=A060679(n) to the equation x^A060679(n)==1 (mod A060679(n)) where A060679(n) are the orders of non-cyclic groups.

1, 1, 3, 2, 1, 3, 1, 7, 5, 7, 2, 1, 7, 4, 1, 8, 3, 3, 15, 1, 11, 1, 2, 15, 11, 3, 2, 1, 15, 6, 9, 7, 17, 4, 7, 2, 1, 15, 1, 8, 31, 3, 7, 3, 23, 1, 4, 3, 11, 31, 26, 1, 23, 1, 7, 11, 3, 2, 1, 31, 13, 2, 39, 3, 15, 2, 1, 35, 19, 2, 15, 11, 7, 8, 1, 31, 10, 1, 3, 24, 35, 63, 2, 3, 7, 1, 8, 31, 3

Offset: 1

Benoit Cloitre, May 10 2002

If there is only one solution 2<=x<=A060679(k) to x^A060679(k)==1 (mod A060679(k)) this solution is : x=A060679(k)-1 (also solution is A060679(k)+1). In this case A060679(k) is a term of A001747(n).

Cf. A060679, A001747, A003277.

for(n=1,200,if(prod(i=2,n-1,(i^n-1)%n)==0,print1(sum(i=2,n-1,if((i^n-1)%n,0,1)),",")))

A001747 2 together with primes multiplied by 2.

Original entry on oeis.org

2, 4, 6, 10, 14, 22, 26, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458, 466, 478, 482, 502

Offset: 1

N. J. A. Sloane

When supplemented with 8, may be considered the "even primes", since these are the even numbers n = 2k which are divisible just by 1, 2, k and 2k. - Louis Zuckerman (louis(AT)trapezoid.com), Sep 12 2000
Sequence gives solutions of sigma(n) - phi(n) = n + tau(n) where tau(n) is the number of divisors of n.
Numbers n such that sigma(n) = 3*(n - phi(n)).
Except for 2, orders of non-cyclic groups k (in A060679(n)) such that x^k==1 (mod k) has only 1 solution 2<=x<=k. - Benoit Cloitre, May 10 2002
Numbers n such that A092673(n) = 2. - Jon Perry, Mar 02 2004
Except for initial terms, this sequence = A073582 = A074845 = A077017. Starting with the term 10, they are identical. - Robert G. Wilson v, Jun 15 2004
Together with 8 and 16, even numbers n such that n^2 does not divide (n/2)!. - Arkadiusz Wesolowski, Jul 16 2011
Twice noncomposite numbers. - Omar E. Pol, Jan 30 2012

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A060679, A009530, A098764.

Equals {2} UNION {A100484}.

Concatenation([2], List([1..60], n-> 2*Primes[n])); # G. C. Greubel, May 18 2019

[2] cat [2*NthPrime(n): n in [1..60]]; // G. C. Greubel, May 18 2019

Join[{2},2*Prime[Range[60]]] (* Harvey P. Dale, Jul 23 2013 *)

print1(2);forprime(p=2,97,print1(", "2*p)) \\ Charles R Greathouse IV, Jan 31 2012

[2]+[2*nth_prime(n) for n in (1..60)] # G. C. Greubel, May 18 2019

a(n) = A001043(n) - A001223(n+1), except for initial term.
a(n) = A116366(n-2,n-2) for n>2. - Reinhard Zumkeller, Feb 06 2006
A006093(n) = A143201(a(n+1)) for n>1. - Reinhard Zumkeller, Aug 12 2008
a(n) = 2*A008578(n). - Omar E. Pol, Jan 30 2012, and Reinhard Zumkeller, Feb 16 2012

A077255 Numbers k such that prime(k)^k == 1 (mod k).

Original entry on oeis.org

2, 4, 5, 6, 8, 10, 12, 14, 16, 18, 20, 24, 27, 32, 36, 40, 42, 48, 50, 52, 54, 60, 64, 70, 72, 80, 84, 96, 100, 105, 108, 110, 114, 120, 121, 124, 125, 126, 128, 136, 144, 148, 156, 160, 162, 168, 180, 181, 182, 189, 192, 200, 210, 216, 220, 231, 234, 240, 243, 246

Offset: 1

Reinhard Zumkeller, Oct 31 2002

nonn

Contains A023143. All terms not in A023143 are in A060679. - Robert Israel, Oct 31 2016

			prime(16)^16 mod 16 = 53^16 mod 16 = 3876269050118516845397872321 mod 16 = 1, therefore 16 is a term.

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

Cf. A000040, A023143, A060679, A077254, A077256.

select(n -> ithprime(n) &^ n mod n = 1, [$1..1000]); # Robert Israel, Oct 31 2016

Select[Range[1000], PowerMod[Prime[#], #, #] == 1&] (* Jean-François Alcover, Dec 16 2021 *)

isok(k) = lift(Mod(prime(k), k)^k) == 1; \\ Michel Marcus, Dec 16 2021

A077254(a(n)) = 1; A077256(n) = A000040(a(n)).

A281856 One fourth of the order of the abelian non-cyclic groups (Z/A033949(n)*Z)^x.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 2, 3, 2, 4, 5, 6, 3, 6, 4, 3, 5, 6, 4, 8, 6, 10, 6, 9, 4, 9, 8, 12, 5, 8, 11, 6, 6, 10, 9, 15, 6, 8, 6, 16, 14, 10, 6, 18, 11, 15, 18, 8, 15, 10, 8, 12, 12, 9, 10, 18, 12, 9, 22, 14, 18, 24, 8, 20, 15, 9, 16, 21, 12, 10, 27, 18, 16, 11, 12, 23

Offset: 1

Wolfdieter Lang, Feb 02 2017

nonn

a(n) is one fourth of the row product of the irregular triangle A281854.

Cf. A000010, A033949, A060679, A281854.

EulerPhi@ Select[Range[2, 130], ! IntegerQ@ PrimitiveRoot@ # &]/4 (* Michael De Vlieger, Feb 02 2017 *)

from sympy import primepi, integer_nthroot, totient
def A281856(n):
    def f(x): return int(n+1+(x>=2)+(x>=4)+sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))+sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return totient(m)>>2 # Chai Wah Wu, Feb 25 2025

a(n) = A000010(A033949(n))/4, n >= 1.

A139392 Odd noncyclic numbers; odd numbers n such that gcd(n,phi(n)) > 1.

Original entry on oeis.org

9, 21, 25, 27, 39, 45, 49, 55, 57, 63, 75, 81, 93, 99, 105, 111, 117, 121, 125, 129, 135, 147, 153, 155, 165, 169, 171, 175, 183, 189, 195, 201, 203, 205, 207, 219, 225, 231, 237, 243, 245, 253, 261, 273, 275, 279, 285, 289, 291, 297, 301, 305, 309, 315, 325

Offset: 1

T. D. Noe, Apr 17 2008

nonn

Sequence A060679 lists all noncyclic numbers, which includes all even numbers >2.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A003277 (cyclic numbers).

Select[Range[1,400,2], GCD[ #,EulerPhi[ # ]]>1&]

is(n)=n%2 && gcd(eulerphi(n),n)>1 \\ Charles R Greathouse IV, Aug 23 2017

A341749 Numbers k such that gcd(k, phi(k)) > log(log(k)).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 66, 68, 70, 72, 74, 75, 76, 78, 80, 81, 82, 84, 86, 88, 90, 92, 93, 94, 96

Offset: 1

Amiram Eldar, Feb 18 2021

nonn

First differs from A080197 at n = 28.
Erdős et al. (2008) proved that the asymptotic density of numbers k such that gcd(k, phi(k)) > (log(log(k)))^u for a real number u > 0 is equal to exp(-gamma) * Integral_{t=u..oo} rho(t) dt, where rho(t) is the Dickman-de Bruijn function and gamma is Euler's constant (A001620). For this sequence u = 1, and therefore its asymptotic density is 1 - exp(-gamma) = 0.43854... (A227242).
There are only 8 cyclic numbers (A003277) in this sequence: 1, 2, 3, 5, 7, 11, 13, 15. All the other terms are in A060679. The first term of A060679 which is not in this sequence is 1622.

			16 is a term since gcd(16, phi(16)) = gcd(16, 8) = 8 > log(log(16)) = 1.0197...
17 is not a term since gcd(17, phi(17)) = gcd(17, 16) = 1 < log(log(17)) = 1.0414...

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Erdős, Florian Luca and Carl Pomerance, On the proportion of numbers coprime to a given integer, in: J.-M. De Koninck, A. Granville and F. Luca (eds.), Anatomy of Integers, AMS, 2008, pp. 47-64.
Wikipedia, Dickman function.

Cf. A000010, A001620, A003277, A009195, A060679, A080130, A227242, A341750.

Select[Range[100], GCD[#, EulerPhi[#]] > Log[Log[#]] &]

isok(k) = (k==1) || (gcd(k, eulerphi(k)) > log(log(k))); \\ Michel Marcus, Feb 19 2021

cp's OEIS Frontend

A070309 Number of solutions 2<=x<=A060679(n) to the equation x^A060679(n)==1 (mod A060679(n)) where A060679(n) are the orders of non-cyclic groups.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A001747 2 together with primes multiplied by 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A077255 Numbers k such that prime(k)^k == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A281856 One fourth of the order of the abelian non-cyclic groups (Z/A033949(n)*Z)^x.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Formula

A139392 Odd noncyclic numbers; odd numbers n such that gcd(n,phi(n)) > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A341749 Numbers k such that gcd(k, phi(k)) > log(log(k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI