A160595 -id:A160595 - cp's OEIS frontend

A340142 Dirichlet inverse of A160595, where A160595(x) = phi(x)/gcd(phi(x), x-1).

1, -1, -1, -1, -1, 0, -1, -1, -2, -2, -1, 1, -1, -4, -2, -1, -1, 1, -1, 1, -1, -8, -1, 2, -4, -10, -4, 9, -1, 6, -1, -1, -3, -14, -10, 3, -1, -16, -10, 4, -1, 4, -1, 1, 5, -20, -1, 3, -6, -5, -14, 17, -1, 4, -18, -10, -7, -26, -1, 8, -1, -28, -9, -1, -1, 24, -1, 1, -9, 30, -1, 4, -1, -34, -5, 25, -13, 22, -1, 7, -8, -38, -1, -5

Offset: 1

Antti Karttunen, Dec 29 2020

sign

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

Cf. A160595.

Cf. also A340141, A340143.

up_to = 65537;
A160595(n) = { my(x=eulerphi(n)); x/gcd(x,n-1); };
DirInverse(v) = { my(u=vector(#v)); u[1] = (1/v[1]); for(n=2, #v, u[n] = -sumdiv(n, d, if(dA160595(n)));
A340142(n) = v340142[n];

A340143 Möbius transform of A160595, where A160595(x) = phi(x)/gcd(phi(x), x-1).

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 2, 2, 3, 0, 1, 0, 5, 3, 4, 0, 2, 0, 3, 2, 9, 0, 2, 4, 11, 6, -3, 0, 0, 0, 8, 4, 15, 11, 4, 0, 17, 11, 6, 0, 3, 0, 9, 0, 21, 0, 4, 6, 12, 15, -5, 0, 6, 19, 18, 8, 27, 0, 3, 0, 29, 13, 16, 2, -11, 0, 15, 10, -12, 0, 8, 0, 35, 12, -7, 14, 0, 0, 12, 18, 39, 0, 13, 15, 41, 27, 18, 0, 12, 3, 21, 14, 45, 35

Offset: 1

Antti Karttunen, Dec 29 2020

sign

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

Cf. A008683, A160595.

Cf. also A340141, A340142.

Table[DivisorSum[n, MoebiusMu[n/#1]*#2/GCD[#2, #3] & @@ {#, EulerPhi[#], # - 1} &], {n, 95}] (* Michael De Vlieger, Dec 29 2020 *)

A160595(n) = { my(x=eulerphi(n)); x/gcd(x,n-1); };
A340143(n) = sumdiv(n,d,moebius(n/d)*A160595(d));

a(n) = Sum_{d|n} A008683(n/d) * A160595(d).

A323373 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => A049559(i) = A049559(j) and A160595(i) = A160595(j).

Original entry on oeis.org

1, 1, 2, 3, 4, 3, 5, 6, 7, 6, 8, 6, 9, 10, 11, 12, 13, 10, 14, 12, 15, 16, 17, 12, 18, 19, 20, 21, 22, 12, 23, 24, 18, 24, 25, 19, 26, 27, 25, 24, 28, 19, 29, 30, 31, 32, 33, 24, 34, 30, 35, 36, 37, 27, 38, 39, 40, 41, 42, 24, 43, 44, 45, 46, 47, 48, 49, 46, 50, 36, 51, 39, 52, 53, 38, 54, 55, 39, 56, 46, 57, 58, 59, 39, 60, 61, 62, 58, 63, 39, 64, 65, 55, 66, 67, 46, 68, 61, 69, 58, 70, 46

Offset: 1

Antti Karttunen, Jan 13 2019

nonn

Restricted growth sequence transform of [A049559(n), A160595(n)].
For all i, j: a(i) = a(j) => A000010(i) = A000010(j).
For all i, j > 1:
  a(i) = a(j) => A323374(i) = A323374(j).

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

Cf. A000010, A049559, A160595, A323374.

Cf. also A323404.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A049559(n) = gcd(eulerphi(n), n-1);
A160595(n) = if(1==n, n, numerator(eulerphi(n)/(n-1)));
v323373 = rgs_transform(vector(up_to, n, [A049559(n), A160595(n)]));
A323373(n) = v323373[n];

A340141 Numerators of the sequence whose Dirichlet convolution with itself yields sequence A160595(x) = phi(x)/gcd(phi(x), x-1).

Original entry on oeis.org

1, 1, 1, 7, 1, 3, 1, 25, 11, 7, 1, 19, 1, 11, 7, 363, 1, 31, 1, 43, 5, 19, 1, 63, 19, 23, 61, 3, 1, 15, 1, 1335, 9, 31, 23, 189, 1, 35, 23, 139, 1, 29, 1, 115, 23, 43, 1, 867, 27, 127, 31, 11, 1, 163, 39, 279, 17, 55, 1, 73, 1, 59, 123, 9923, 5, -15, 1, 187, 21, -9, 1, 615, 1, 71, 127, 19, 29, 47, 1, 1875, 1363, 79, 1, 203, 31

Offset: 1

Antti Karttunen, Dec 29 2020

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

Cf. A046644 (denominators).
Cf. A160595.
Cf. also A340142, A340143.

up_to = 65537;
A160595(n) = { my(x=eulerphi(n)); x/gcd(x,n-1); };
DirSqrt(v) = {my(n=#v, u=vector(n)); u[1]=1; for(n=2, n, u[n]=(v[n]/v[1] - sumdiv(n, d, if(d>1&&dA160595(n)));
A340141(n) = numerator(v340141rat[n]);

A049559 a(n) = gcd(n - 1, phi(n)).

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 4, 1, 46, 1, 6, 1, 2, 3, 52, 1, 2, 1, 4, 1, 58, 1, 60, 1, 2, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 2, 3, 4, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 18, 1, 4

Offset: 1

Labos Elemer, Dec 28 2000

nonn

For prime n, a(n) = n - 1. Question: do nonprimes exist with this property?
Answer: No. If n is composite then a(n) < n - 1. - Charles R Greathouse IV, Dec 09 2013
Lehmer's totient problem (1932): are there composite numbers n such that a(n) = phi(n)? - Thomas Ordowski, Nov 08 2015
a(n) = 1 for n in A209211. - Robert Israel, Nov 09 2015

			a(9) = 2 because phi(9) = 6 and gcd(8, 6) = 2.
a(10) = 1 because phi(10) = 4 and gcd(9, 4) = 1.

Richard K. Guy, Unsolved Problems in Number Theory, B37.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Lehmer's Totient Problem

Cf. A000010, A002322, A039766, A063994, A160595, A209211, A219428, A264012, A264024, A280262, A283656, A283872, A284089, A284440, A318827, A318829, A318830, A330747 (ordinal transform), A340195.

Cf. also A009195, A058515, A058663, A187730, A258409, A339964, A340071, A340081, A340087 for more or less analogous sequences.

[Gcd(n-1, EulerPhi(n)): n in [1..80]]; // Vincenzo Librandi, Oct 13 2018

seq(igcd(n-1, numtheory:-phi(n)), n=1..100); # Robert Israel, Nov 09 2015

Table[GCD[n - 1, EulerPhi[n]], {n, 93}] (* Michael De Vlieger, Nov 09 2015 *)

a(n)=gcd(eulerphi(n),n-1) \\ Charles R Greathouse IV, Dec 09 2013

from sympy import totient, gcd
print([gcd(totient(n), n - 1) for n in range(1, 101)]) # Indranil Ghosh, Mar 27 2017

a(p^m) = a(p) = p - 1 for prime p and m > 0. - Thomas Ordowski, Dec 10 2013
From Antti Karttunen, Sep 09 2018: (Start)
a(n) = A000010(n) / A160595(n) = A063994(n) / A318829(n).
a(n) = n - A318827(n) = A000010(n) - A318830(n).
(End)
a(n) = gcd(A000010(n), A219428(n)) = gcd(A000010(n), A318830(n)). - Antti Karttunen, Jan 05 2021

A339901 a(n) = A339971(n) / gcd(A339809(2*n), A339971(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 3, 1, 5, 5, 5, 15, 3, 5, 15, 1, 3, 3, 3, 1, 9, 9, 9, 15, 15, 5, 15, 9, 45, 5, 45, 1, 1, 1, 1, 3, 3, 1, 3, 5, 1, 5, 5, 5, 15, 15, 15, 3, 3, 1, 3, 9, 9, 3, 9, 1, 15, 15, 15, 15, 9, 45, 45, 1, 9, 9, 9, 9, 27, 27, 27, 45, 45, 5, 45, 135, 135, 45, 135, 9, 27, 27, 27, 3, 81, 81, 81, 135, 27, 45, 135, 405

Offset: 0

Antti Karttunen, Dec 28 2020

Compare also to the scatter plot of A339898.

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

Cf. A000265, A053575, A019565, A160595, A339809, A339821, A339971, A339898, A339899, A340075, A340085.

Cf. A339973 (positions of ones).

A000265(n) = (n>>valuation(n,2));
A019565(n) = { my(m=1, p=1); while(n>0, p = nextprime(1+p); if(n%2, m *= p); n >>= 1); (m); };
A339901(n) = { my(x=A019565(2*n), y=A000265(eulerphi(x))); y/gcd((x-1),y); };

a(n) = A339971(n) / A339899(n).
a(n) = A000265(A160595(A019565(2*n))).
a(n) = A340075(A019565(n)) = A340085(A019565(2*n)).

A340072 a(n) = phi(x) / gcd(x-1, phi(x)), where x = A003961(n), i.e., n with its prime factorization shifted one step towards larger primes.

Original entry on oeis.org

1, 1, 1, 3, 1, 4, 1, 9, 5, 3, 1, 6, 1, 5, 12, 27, 1, 20, 1, 18, 20, 12, 1, 36, 7, 16, 25, 30, 1, 6, 1, 81, 3, 9, 15, 15, 1, 11, 16, 27, 1, 20, 1, 18, 20, 28, 1, 54, 11, 42, 36, 12, 1, 100, 4, 45, 44, 15, 1, 72, 1, 36, 100, 243, 48, 48, 1, 54, 7, 12, 1, 180, 1, 40, 42, 66, 60, 64, 1, 162, 125, 21, 1, 120, 9, 23, 60, 108

Offset: 1

Antti Karttunen, Dec 28 2020

nonn

Prime shifted analog of A160595.

Antti Karttunen, Table of n, a(n) for n = 1..8191
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A000010, A003961, A003972, A160595, A253885, A340071, A340073, A340075 (gives the odd part).

Cf. also A340082.

f:= proc(n) local F,x,p,t;
  F:= ifactors(n)[2];
  x:= mul(nextprime(t[1])^t[2],t=F);
  p:= numtheory:-phi(x);
  p/igcd(x-1,p)
end proc:
map(f,[$1..100]); # Robert Israel, Dec 28 2020

a[n_] := Module[{x, p, e, phi}, x = Product[{p, e} = pe; NextPrime[p]^e, {pe, FactorInteger[n]}]; phi = EulerPhi[x]; phi/GCD[x-1, phi]];
Array[a, 100] (* Jean-François Alcover, Jan 04 2022 *)

A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A340072(n) = { my(x=A003961(n), u=eulerphi(x)); u/gcd(x-1, u); };

a(n) = A160595(A003961(n)).

a(n) = A003972(n) / A340071(n).

A340082 a(n) = A003958(n) / gcd(n-1, A003958(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 6, 4, 1, 1, 4, 1, 4, 3, 10, 1, 2, 2, 12, 4, 2, 1, 8, 1, 1, 5, 16, 12, 4, 1, 18, 12, 4, 1, 12, 1, 10, 4, 22, 1, 2, 3, 16, 16, 4, 1, 8, 20, 6, 9, 28, 1, 8, 1, 30, 12, 1, 3, 4, 1, 16, 11, 8, 1, 4, 1, 36, 16, 6, 15, 24, 1, 4, 1, 40, 1, 12, 16, 42, 28, 10, 1, 16, 4, 22, 15, 46, 36, 2, 1, 36

Offset: 1

Antti Karttunen, Dec 28 2020

nonn

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

Cf. A003958, A340081, A340083, A340085 (gives the odd part).

Cf. also A160595, A340072.

A003958(n) = if(1==n,n,my(f=factor(n)); for(i=1,#f~,f[i,1]--); factorback(f));
A340082(n) = { my(u=A003958(n)); u/gcd(n-1, u); };

a(n) = A003958(n) / A340081(n) = A003958(n) / gcd(n-1, A003958(n)).

A340085 a(n) = A336466(n) / gcd(n-1, A336466(n)); Odd part of A340082(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 3, 5, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 5, 1, 3, 1, 1, 9, 3, 1, 1, 3, 1, 5, 1, 11, 1, 1, 3, 1, 1, 1, 1, 1, 5, 3, 9, 7, 1, 1, 1, 15, 3, 1, 3, 1, 1, 1, 11, 1, 1, 1, 1, 9, 1, 3, 15, 3, 1, 1, 1, 5, 1, 3, 1, 21, 7, 5, 1, 1, 1, 11, 15, 23, 9, 1, 1, 9, 5, 1, 1, 1, 1, 3, 3

Offset: 1

Antti Karttunen, Dec 28 2020

nonn

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

Cf. A000265, A003958, A003961, A019565, A336466, A339901, A340082, A340084, A340086.

Cf. also A160595.

Array[#2/GCD[#1 - 1, #2] & @@ {#, Times @@ Map[If[# <= 2, 1, (# - 1)/2^IntegerExponent[# - 1, 2]] &, Flatten[ConstantArray[#1, #2] & @@@ FactorInteger[#]]]} &, 105] (* Michael De Vlieger, Dec 29 2020 *)

A000265(n) = (n>>valuation(n,2));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,if(2==f[k,1],1,(A000265(f[k,1]-1))^f[k,2])); };
A340085(n) = { my(u=A336466(n)); u/gcd(n-1, u); };

a(n) = A000265(A340082(n)).
a(n) = A336466(n) / A340084(n) = A336466(n) / gcd(n-1, A336466(n)).
For all n >= 0, a(A003961(A019565(n))) = a(A019565(2*n)) = A339901(n).

A318829 a(n) = A063994(n) / A049559(n) = (1/gcd(n-1, phi(n))) * Product_{primes p dividing n} gcd(p-1, n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2

Offset: 1

Antti Karttunen, Sep 09 2018

nonn

Records occur at: 1, 15, 85, 247, 671, 949, 1105, 1387, 2047, 2821, 9471, 11305, 13747, 13981, 29341, 40885, 51319, 63973, ...

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

Cf. A049559, A063994, A160595, A247074, A318828.

A049559(n) = gcd(eulerphi(n), n-1); \\ From A049559
A063994(n) = { my(f=factor(n)[,1]); prod(i=1, #f, gcd(f[i]-1, n-1)); };
A318829(n) = (A063994(n)/A049559(n));

a(n) = A063994(n) / A049559(n).

a(n) = A160595(n) / A247074(n).

cp's OEIS Frontend

A340142 Dirichlet inverse of A160595, where A160595(x) = phi(x)/gcd(phi(x), x-1).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A340143 Möbius transform of A160595, where A160595(x) = phi(x)/gcd(phi(x), x-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A323373 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => A049559(i) = A049559(j) and A160595(i) = A160595(j).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A340141 Numerators of the sequence whose Dirichlet convolution with itself yields sequence A160595(x) = phi(x)/gcd(phi(x), x-1).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A049559 a(n) = gcd(n - 1, phi(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A339901 a(n) = A339971(n) / gcd(A339809(2*n), A339971(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A340072 a(n) = phi(x) / gcd(x-1, phi(x)), where x = A003961(n), i.e., n with its prime factorization shifted one step towards larger primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A340082 a(n) = A003958(n) / gcd(n-1, A003958(n)).

Views

Author

Keywords

Links

Crossrefs