A050399 -id:A050399 - cp's OEIS frontend

A009195 a(n) = gcd(n, phi(n)).

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 4, 3, 2, 1, 8, 5, 2, 9, 4, 1, 2, 1, 16, 1, 2, 1, 12, 1, 2, 3, 8, 1, 6, 1, 4, 3, 2, 1, 16, 7, 10, 1, 4, 1, 18, 5, 8, 3, 2, 1, 4, 1, 2, 9, 32, 1, 2, 1, 4, 1, 2, 1, 24, 1, 2, 5, 4, 1, 6, 1, 16, 27, 2, 1, 12, 1, 2, 1, 8, 1, 6, 1, 4, 3, 2, 1, 32, 1, 14, 3, 20

Offset: 1

David W. Wilson

The inequality gcd(n, phi(n)) <= 2n exp(-sqrt(log 2 log n)) holds for all squarefree n >= 1 (Erdős, Luca, and Pomerance).

Erdős shows that for almost all n, a(n) ~ log log log log n. - Charles R Greathouse IV, Nov 23 2011

T. D. Noe, Table of n, a(n) for n = 1..10000
Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 75-78.
Paul Erdős, Florian Luca, Carl Pomerance, On the proportion of numbers coprime to a given integer, in Anatomy of Integers, pp. 47-64, J.-M. De Koninck, A. Granville, F. Luca (editors), AMS, 2008.
Joshua Stucky, The distribution of gcd(n,phi(n)), arXiv:2402.13997 [math.NT], 2024.

Cf. A000010, A003277, A050399, A051953, A061303, A109395, A285711.

a009195 n = n `gcd` a000010 n  -- Reinhard Zumkeller, Feb 27 2012

[Gcd(n, EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Dec 17 2015

a009195 := n -> igcd(i,numtheory[phi](n));

Table[GCD[n,EulerPhi[n]],{n,100}] (* Harvey P. Dale, Aug 11 2011 *)

a(n)=gcd(n,eulerphi(n)) \\ Charles R Greathouse IV, Nov 23 2011

def a009195(n):
    from math import gcd
    phi = lambda x: len([i for i in range(x) if gcd(x,i) == 1])
    return gcd(n, phi(n))
# Edward Minnix III, Dec 05 2015

a(n) = gcd(n, A051953(n)). - Labos Elemer

a(n) = n / A109395(n). - Antti Karttunen, May 04 2017 (corrected also typo in above formula).

A072994 Number of solutions to x^n==1 (mod n), 1<=x<=n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 8, 1, 6, 1, 8, 3, 2, 1, 8, 5, 2, 9, 4, 1, 4, 1, 16, 1, 2, 1, 12, 1, 2, 3, 16, 1, 12, 1, 4, 3, 2, 1, 16, 7, 10, 1, 8, 1, 18, 5, 8, 3, 2, 1, 16, 1, 2, 9, 32, 1, 4, 1, 8, 1, 4, 1, 24, 1, 2, 5, 4, 1, 12, 1, 32, 27, 2, 1, 24, 1, 2, 1, 8, 1, 12, 1, 4, 3

Offset: 1

Benoit Cloitre, Aug 21 2002

More generally, if the equation a(x)*m=x has solutions, solutions are congruent to m: a(x)*7=x for x=7, 14, 21, 28, 49, 56, 63, 98, 112, ... . There are some composite values of m such that a(x)*m=x has solutions, as m=15. a(n) coincides with A009195(n) at many values of n, but not at n = 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, ... . It seems also that for n large enough sum_{k=1..n} a(k) > n*log(n)*log(log(n)).

Similar (if not the same) coincidences and differences occur between A072995 and A050399. Sequence A072989 lists these indices. - M. F. Hasler, Feb 23 2014

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

1, seq(nops(select(t -> t^n mod n = 1, [$1..n-1])),n=2..100); # Robert Israel, Dec 07 2014

f[n_] := (d = If[ OddQ@ n, 1, 2]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = f[2] = 1; Array[f, 93] (* or *)
f[n_] := Length@ Select[ Range@ n, PowerMod[#, n, n] == 1 &]; f[n_] := 1 /; n<2; Array[f, 93] (* Robert G. Wilson v, Dec 06 2014 *)

A072994=n->sum(k=1,n,Mod(k,n)^n==1) \\ M. F. Hasler, Feb 23 2014

For n>0, a(A003277(n)) = 1, a(2^n) = 2^(n-1), a(A065119(n)) = A065119(n)/3.

For n>1, a(A026383(n)) = A026383(n)/5.

Corrected by T. D. Noe, May 19 2007

A072995 Least k > 0 such that the number of solutions to x^k == 1 (mod k) 1 <= x <= k is equal to n, or 0 if no such k exists.

Original entry on oeis.org

1, 4, 9, 8, 25, 18, 49, 16, 27, 50, 121, 36, 169, 98, 225, 32, 289, 54, 361, 110, 147, 242, 529, 72, 125, 338, 81, 196, 841, 0, 961, 64, 1089, 578, 1225, 108, 1369, 722, 507, 100, 1681, 0, 1849, 484, 675, 1058, 2209, 144, 343, 250, 2601, 1378, 2809

Offset: 1

Benoit Cloitre, Aug 21 2002

nonn

A072989 lists the indices for which a(n) differs from A050399(n), e.g., in n = 20, 40, 52, ... in addition to the zeros in this sequence (n = 30, 42, 66, 70, 78, 90, ...). See also A009195 vs. A072994. [Corrected and extended by M. F. Hasler, Feb 23 2014]
The sequence seems difficult to extend, as the next term a(30) is larger than 5100. However, a(32)=64, a(64)=128 and a(128)=256 can be easily calculated. It thus appears that a(2^k)=2^(k+1), for k=1,2,3,.... Is this known to be true? - John W. Layman, Aug 05 2003 -- Answer: It's true. One could have defined the sequence so that a(1)=2: then it would be true for 2^0 also. - Don Reble, Feb 23 2014
a(30), if it exists, is greater than 400000. - Ryan Propper, Sep 10 2005
a(30) doesn't exist: If N is even, and divisible by D different odd primes, but not divisible by 2^D, then a(N) doesn't exist. - Don Reble, Feb 23 2014 [This and the preceding comment refer to the former definition lacking the clause "0 if no such k exists". - Ed.]
Conjecture: a(n)=0 iff n/2 is in A061346. - Robert G. Wilson v, Feb 23 2014
[n=420 seems to be a counterexample to the above conjecture. - M. F. Hasler, Feb 24 2014]
From Robert G. Wilson v, Mar 05 2014: (Start)
Observation:
If n = 1 then a(n) = 1 by definition;
If, but not iff, n (an even number) is a member of A238367 then a(n) = 0;
If n (an even number not in A238367) is {684, 954, ...}, then a(n) = 0;
If n (an odd number) is {273, 399, 651, 741, 777, 903, ...}, then a(n) = 0;
If p is a prime [A000040] and e is its exponent, then a(p^e) = p^(e+1);
If p is a prime then a(2p^e) = 2p^(e+1);
If p is a prime then a(n) # p since the f(p)=1.
(End)
Often A072995(n) equals A050399(n). They differ at n: 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, 102, 104, 110, 114, 116, 120, 126, 130, 132, ... - Robert G. Wilson v, Dec 06 2014
When A072995(n)>0 and does not equal A050399(n): 20, 40, 52, 60, 68, 80, 84, 100, 104, 116, 120, 132, 136, 140, 148, 156, 160, 164, 168, 171, 180, 200, ... - Robert G. Wilson v, Dec 06 2014
When a(n) > 1, then 2n <= a(n) <= n^2. - Robert G. Wilson v, Dec 10 2014

Robert G. Wilson v, Table of n, a(n) for n = 1..1013 (first 200 terms from Don Reble)
Robert G. Wilson v, Graph of n, a(n) for n = 1..1000

Cf. A072994.

t = Table[0, {1000}]; f[n_] := (d = If[EvenQ@ n, 2, 1]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = 1; k = 1; While[k < 520001, If[ PrimeQ@ k, k++]; a = f@ k; If[a < 1001 && t[[a]] == 0, t[[a]] = k; Print[{a, k}]]; k++]; t (* Robert G. Wilson v, Dec 12 2014 *)

A072995(n)=(n%2||n%2^(omega(n)-1)==0)&&for(k=1,9e9,A072994(k)==n&&return(k)) \\ M. F. Hasler, Feb 23 2014

First occurrence of n in A072994.

More terms from Don Reble, Feb 23 2014

Edited, at the suggestion of Don Reble, by M. F. Hasler, Feb 23 2014

A074389 a(n) = gcd(n, sigma(n), phi(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 6, 1, 4, 3, 2, 1, 4, 1, 1, 1, 2, 1, 6, 1, 8, 1, 2, 1, 4, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 4, 1, 6, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 6, 1, 4, 1, 2, 1, 4, 1, 1, 3, 1, 1, 2, 1, 2, 3

Offset: 1

Labos Elemer, Aug 23 2002

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A000203, A073815, A050399, A009194, A009195, A009223, A074465, A074466.

In the old definition the erroneously given formula gcd(n, A000005(n), A000010(n)) is now sequence A318459. - Antti Karttunen, Sep 07 2018

Table[Apply[GCD, {w, DivisorSigma[1, w], EulerPhi[w]}], {w, 1, 128}]

A074389(n) = gcd([n, sigma(n), eulerphi(n)]); \\ Antti Karttunen, Sep 07 2018

a(n) = gcd(n, A000010(n), A000203(n)).

a(n) = gcd(n, A009223(n)). - Antti Karttunen, Sep 07 2018

Name corrected by Antti Karttunen, Sep 07 2018

A129598 a(n) = n * A111089(n).

Original entry on oeis.org

2, 4, 9, 8, 25, 18, 49, 16, 27, 50, 121, 36, 169, 98, 75, 32, 289, 54, 361, 100, 147, 242, 529, 72, 125, 338, 81, 196, 841, 150, 961, 64, 363, 578, 245, 108, 1369, 722, 507, 200, 1681, 294, 1849, 484, 225, 1058, 2209, 144, 343, 250, 867, 676, 2809, 162, 605

Offset: 1

Antti Karttunen, May 01 2007

nonn

Conjecture: differs from A050399 at the positions given by A089966. E.g., a(15)=75, instead of A050399(15)=225, a(30)=150, instead of A050399(30)=450, a(33)=363, instead of A050399(33)=1089, a(45)=225, instead of A050399(45)=1225. Conjecture 2: for all n > 1, a(n) divides A050399(n).

Antti Karttunen, Table of n, a(n) for n = 1..10000
G. Guninski, List of automatically found conjectural relations between this and other sequences

Row 2 of A129595.
Essentially the same as A253560, except that here we have a(1) = 2.
Cf. also A050399, A089966, A111089, A072995.

Join[{2},Table[n*Last@(First/@FactorInteger[n]),{n,2,200}]] (* Vladimir Joseph Stephan Orlovsky, Apr 08 2011 *)

a(1) = 2; for n >= 2, a(n) = A253560(n).

A074391 a(n) is the smallest number such that gcd(a(n), sigma(a(n))) = n.

Original entry on oeis.org

1, 10, 15, 12, 95, 6, 91, 56, 153, 40, 473, 24, 117, 182, 135, 336, 1139, 90, 703, 380, 861, 946, 3151, 168, 3725, 468, 1431, 28, 5017, 570, 775, 992, 891, 2176, 4865, 792, 2701, 1406, 585, 280, 6683, 546, 11051, 1892, 1305, 6302, 13207, 528, 4753, 5800

Offset: 1

Labos Elemer, Aug 23 2002

nonn

a(n) is the smallest number k such that A017666(k), the denominator of sigma(k)/k, is equal to k/n. - Jaroslav Krizek, Sep 23 2014

Each term a(n) is divisible by its index n. - Michel Marcus, Jan 13 2015

			n=6: a(6)=6 because gcd(6, sigma(6))=6 and a(6)=6 is the smallest.

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

Cf. A000203, A017666, A073815, A050399, A009195, A009194.

A074391:=func; [A074391(n): n in[1..100]] // Jaroslav Krizek, Sep 23 2014

f:= proc(n) local k;
  for k from n by n do
    if igcd(k, numtheory:-sigma(k))=n then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Feb 11 2020

f[x_] := GCD[DivisorSigma[1, x], x] t=Table[0, {100}]; Do[s=f[n]; If[s<101&&t[[s]]==0, t[[s]]=n], {n, 1, 1000000}];

a(n) = my(k=1); while (gcd(sigma(k), k) != n, k++); k; \\ Michel Marcus, Jan 13 2015

a(n) = Min{x; gcd(x, sigma(x))} = Min{x; gcd(x, A000203(x))} = n. - corrected by Michel Marcus, Jan 13 2015

A074390 a(n) is the least number k that A074389(k) = n.

Original entry on oeis.org

1, 6, 18, 12, 200, 42, 196, 56, 459, 950, 5203, 396, 9243, 980, 1800, 336, 19363, 270, 13357, 600, 1764, 10406, 72473, 168, 18625, 34814, 4293, 812, 145493, 1350, 15376, 992, 19602, 38726, 41615, 1836, 99937, 26714, 1521, 440, 274003, 3822, 475193

Offset: 1

Labos Elemer, Aug 23 2002

nonn

			For n = 79: a(79) = 979837 because GCD(979837,998718,961272) = 79 and 979837 is the smallest.

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

Cf. A000005, A000010, A073815, A050399, A009195, A009194.

f[x_] := GCD[DivisorSigma[1, x], EulerPhi[x], x]; t=Table[0, {100}]; Do[s=f[n]; If[s<101&&t[[s]]==0, t[[s]]=n], {n, 1, 1000000}]; t

lista(len) = {my(v = vector(len), c = 0, k = 1, f, i); while(c < len, f = factor(k); i = gcd([k, sigma(k), eulerphi(k)]); if(i <= len && v[i] == 0, c++; v[i] = k); k++); v;} \\ Amiram Eldar, Nov 14 2024

a(n) = Min{x; GCD(x, sigma(x), phi(x)) = n} = Min{x; GCD(x, A000005(x), A000010(x)) = n}.

cp's OEIS Frontend

A009195 a(n) = gcd(n, phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

A072994 Number of solutions to x^n==1 (mod n), 1<=x<=n.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

PARI

Formula

Extensions

A072995 Least k > 0 such that the number of solutions to x^k == 1 (mod k) 1 <= x <= k is equal to n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A074389 a(n) = gcd(n, sigma(n), phi(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A129598 a(n) = n * A111089(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A074391 a(n) is the smallest number such that gcd(a(n), sigma(a(n))) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A074390 a(n) is the least number k that A074389(k) = n.

Views

Author

Keywords

Examples