A009195 -id:A009195 - cp's OEIS frontend

A082067 Smallest prime that divides n and phi(n)=A000010(n), or 1 if n and phi(n) are relatively prime.

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 7, 2, 1, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 5, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3

Offset: 1

Labos Elemer, Apr 07 2003

nonn

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

Cf. A000010, A009195.

Cf. also A082061, A082068, A082069, A082070, A082071, A082072.

ffi[x_] := Flatten[FactorInteger[x]]; lf[x_] := Length[FactorInteger[x]]; ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}]; f1[x_] := n; f2[x_] := EulerPhi[x]; Table[Min[Intersection[ba[f1[w]], ba[f2[w]]]], {w, 1, 128}]
(* Second program: *)
Array[If[CoprimeQ[#1, #2], 1, Min@ Apply[Intersection, Map[FactorInteger[#][[All, 1]] &, {#1, #2}]]] & @@ {#, EulerPhi@ #} &, 105] (* Michael De Vlieger, Nov 03 2017 *)

A020639(n) = if(1==n,n,vecmin(factor(n)[, 1]));
A082067(n) = A020639(gcd(eulerphi(n), n)); \\ Antti Karttunen, Nov 03 2017

a(n) = A020639(A009195(n)). - Antti Karttunen, Nov 03 2017

Name clarified by Antti Karttunen, Nov 03 2017

A342413 a(n) = gcd(phi(n), A003415(n)), where A003415(n) is the arithmetic derivative of n, and phi is Euler totient function.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Mar 11 2021

nonn

Antti Karttunen, Table of n, a(n) for n = 1..12500
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000010, A003415, A003557, A166374, A342009, A342414, A342415, A342416.

Cf. also A009195, A085731.

Array[GCD[If[# < 2, 0, # Total[#2/#1 & @@@ FactorInteger[#]]], EulerPhi[#]] &@ Abs[#] &, 100] (* Michael De Vlieger, Mar 11 2021 *)

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A342413(n) = gcd(eulerphi(n), A003415(n));

a(n) = gcd(A000010(n), A003415(n)).
a(n) = A003415(n) / A342414(n) = A000010(n) / A342415(n).
a(n) = A003557(n) * A342416(n).

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

A323409 Greatest common divisor of Product (p_i^e_i)-1 and n, when n = Product (p_i^e_i); a(n) = gcd(n, A047994(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 6, 1, 2, 1, 1, 1, 2, 1, 4, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 12, 1, 2, 3, 4, 1, 6, 1, 2, 1, 2, 1, 6, 1, 2, 1, 4, 1, 2, 5, 14, 3, 2, 1, 12, 1, 2, 3, 1, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 3, 2, 1, 6, 1, 20, 1, 2, 1, 12, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 3

Offset: 1

Antti Karttunen, Jan 15 2019

nonn

Records 1, 2, 6, 12, 14, 20, 24, 84, 120, 168, 240, 468, 720, 1008, 1240, 1488, 1632, 7440, 9360, 14880, 32640, ... occur at n = 1, 6, 12, 36, 56, 80, 144, 168, 240, 504, 720, 1404, 3600, 4032, 4960, 8928, 13056, 14880, 28080, 44640, 65280, ...

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A047994, A323410.

Cf. also A009195, A323166, A323406.

A047994(n) = { my(f=factor(n)~); prod(i=1, #f, f[1, i]^f[2, i]-1); };
A323409(n) = gcd(n, A047994(n));

a(n) = gcd(n, A047994(n)), where A047994 is unitary phi.

A331175 Number of values of k, 1 <= k <= n, with A109395(k) = A109395(n), where A109395(n) = n/gcd(n, phi(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 11 2020

nonn

Ordinal transform of A109395.

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

Cf. A000010, A003277, A009195, A109395.

Cf. also A081373, A330746, A331177.

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
A109395(n) = n/gcd(n, eulerphi(n));
v331175 = ordinal_transform(vector(up_to, n, A109395(n)));
A331175(n) = v331175[n];

For n >= 1, a(2^n) = n, a(A003277(n)) = 1.

A076511 Numerator of cototient(n)/totient(n).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 4, 7, 1, 1, 2, 1, 3, 3, 6, 1, 2, 1, 7, 1, 4, 1, 11, 1, 1, 13, 9, 11, 2, 1, 10, 5, 3, 1, 5, 1, 6, 7, 12, 1, 2, 1, 3, 19, 7, 1, 2, 3, 4, 7, 15, 1, 11, 1, 16, 3, 1, 17, 23, 1, 9, 25, 23, 1, 2, 1, 19, 7, 10, 17, 9, 1, 3, 1, 21, 1, 5, 21, 22, 31, 6, 1, 11, 19, 12, 11

Offset: 1

Reinhard Zumkeller, Oct 15 2002

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

Cf. A076512 (denominators), A000010, A009195, A051953, A082695, A109395.

Table[Numerator[n/EulerPhi[n] - 1], {n, 1, 100}] (* Amiram Eldar, Nov 21 2022 *)

A076511(n) = numerator((n-eulerphi(n))/eulerphi(n)); \\ Antti Karttunen, Sep 07 2018

a(n) = A051953(n)/A009195(n).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k)/A076512(k) = zeta(2)*zeta(3)/zeta(6) - 1 = A082695 - 1 = 0.943596... . Amiram Eldar, Nov 21 2022

A285711 a(n) = gcd(A051953(n), A079277(n)), a(1) = 1.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 26 2017

nonn

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

Cf. A009195, A051953, A079277, A285707, A285709, A285710.

Table[GCD[n - EulerPhi@ n, If[n <= 2, 1, Module[{k = n - 2, e = Floor@ Log2@ n}, While[PowerMod[n, e, k] != 0, k--]; k]]], {n, 115}] (* Michael De Vlieger, Apr 26 2017 *)

from sympy import divisors, totient, gcd
from sympy.ntheory.factor_ import core
def a007947(n): return max(i for i in divisors(n) if core(i) == i)
def a079277(n):
    k=n - 1
    while True:
        if a007947(k*n) == a007947(n): return k
        else: k-=1
def a(n): return 1 if n==1 else gcd(n - totient(n), a079277(n))
print([a(n) for n in range(1, 151)]) # Indranil Ghosh, Apr 26 2017

(define (A285711 n) (if (= 1 n) n (gcd (A051953 n) (A079277 n))))

a(1) = 1; for n > 1, a(n) = gcd(A051953(n), A079277(n)).

A072989 Numbers m>0 such that the number of solutions to x^m==1 (mod m), 1<=x<=m, is not equal to gcd(m, phi(m)).

Original entry on oeis.org

20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, 102, 104, 110, 114, 116, 120, 126, 130, 132, 136, 138, 140, 148, 150, 154, 156, 160, 164, 168, 170, 171, 174, 180, 182, 186, 190, 198, 200, 204, 208, 210, 212, 220, 222, 228, 230, 232, 234, 238, 240

Offset: 1

Benoit Cloitre, Aug 21 2002

Conjecture: limit of a(n)/n is zero.

This conjecture is certainly wrong as stated, because sequences "Numbers such that..." have lim a(n)/n >= 1 and a(n) > n for all indices following the first one for which this holds, as here: a(1) > 1. - M. F. Hasler, Feb 24 2014

Robert G. Wilson v, Table of n, a(n) for n = 1..220

Cf. A009195, A072994.

isok(m) = sum(x=1, m, Mod(x, m)^m==1) != gcd(m, eulerphi(m)); \\ Michel Marcus, Feb 18 2021

Equals { m>0 | A009195(m) != A072994(m) }. - M. F. Hasler, Feb 23 2014

A285707 a(n) = gcd(n, A079277(n)), a(1) = 1.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 26 2017

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

Cf. A009195, A079277, A285699, A285708, A285711.

Table[GCD[n, #] &@ If[n <= 2, 1, Module[{k = n - 2, e = Floor@ Log2@ n}, While[PowerMod[n, e, k] != 0, k--]; k]], {n, 117}] (* Michael De Vlieger, Apr 26 2017 *)

A007947(n) = factorback(factorint(n)[, 1]);
A079277(n) = { my(r); if((n > 1 && !bitand(n,(n-1))), (n/2), r=A007947(n); if(1==n,0,k = n-1; while(A007947(k*n) <> r, k = k-1); k)); };
A285707(n) = if(1==n,n,gcd(A079277(n),n));

from sympy import divisors, gcd
from sympy.ntheory.factor_ import core
def a007947(n):
    return max(i for i in divisors(n) if core(i) == i)
def a079277(n):
    k=n - 1
    while True:
        if a007947(k*n) == a007947(n): return k
        else: k-=1
def a(n): return 1 if n==1 else gcd(n, a079277(n))
print([a(n) for n in range(1, 151)]) # Indranil Ghosh, Apr 26 2017

(define (A285707 n) (if (= 1 n) n (gcd n (A079277 n))))

a(1) = 1; for n > 1, a(n) = gcd(n, A079277(n)) = gcd(n, A285699(n)).

a(n) = n / A285708(n).

cp's OEIS Frontend

A082067 Smallest prime that divides n and phi(n)=A000010(n), or 1 if n and phi(n) are relatively prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A342413 a(n) = gcd(phi(n), A003415(n)), where A003415(n) is the arithmetic derivative of n, and phi is Euler totient function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A323409 Greatest common divisor of Product (p_i^e_i)-1 and n, when n = Product (p_i^e_i); a(n) = gcd(n, A047994(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A331175 Number of values of k, 1 <= k <= n, with A109395(k) = A109395(n), where A109395(n) = n/gcd(n, phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A076511 Numerator of cototient(n)/totient(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A285711 a(n) = gcd(A051953(n), A079277(n)), a(1) = 1.

Views

Author

Keywords

Links