A264012 -id:A264012 - cp's OEIS frontend

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

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

A280262 Numbers n such that A187730(n) < A049559(n).

Original entry on oeis.org

21, 33, 57, 65, 69, 77, 91, 93, 105, 129, 133, 141, 145, 161, 177, 185, 189, 201, 209, 213, 217, 225, 237, 249, 253, 265, 273, 297, 301, 305, 309, 321, 329, 341, 345, 369, 377, 381, 385, 393, 413, 417, 437, 441, 451, 453, 465, 469, 473, 481, 489, 497, 501, 505, 513, 517, 537, 545, 553, 559, 573

Offset: 1

Thomas Ordowski and Robert Israel, Dec 30 2016

nonn

Terms are not of the form p^k, where p is a prime.
There are no terms of the form 2p+1, where p is a prime.
The sequence contains all Carmichael numbers except A264012.
If n is in the sequence, then n-1 is not squarefree. - Thomas Ordowski, Jan 02 2017
Theorem: the set of such numbers has natural density 0. Proof: Let y = y(n) = loglog n /logloglog n. Using part 1 of Lemma 2.1 in paper 199 on my home page (joint with Luca), applied to the residue class 1: But for a set of n of density 0, for each integer d < y, there is a prime p|n with p == 1 (mod d). In particular, lambda(n) is divisible by every integer d up to y. Suppose now that gcd(lambda(n),n-1) < gcd(phi(n),n-1). Then there is a prime power q^a such that q^a | phi(n), q^a | n-1, and q^a does not divide lambda(n). Then, but for a set of n of density 0, we would have q^a > y. Since q | lambda(n), we have a at least 2. So, n-1 is divisible by some q^a > y with a >= 2. The set of such n has density 0. QED. - Carl Pomerance, Jan 02 2017
Number of terms < 10^k: 0, 8, 112, 1258, 13069, 132262, 1324263, 13229372, 132009236, ..., . Robert G. Wilson v, Jan 04 2017
If p and q are distinct primes == 3 (mod 4), then p*q is in the sequence. - Thomas Ordowski, Mar 30 2017

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

Subsequence of A033949.

Cf. A000010, A002322, A049559, A187730.

select(t -> igcd(numtheory:-lambda(t),t-1) < igcd(numtheory:-phi(t),t-1), [$1..1000]);

Select[Range@ 600, GCD[CarmichaelLambda@ #, # - 1] < GCD[# - 1, EulerPhi@ #] &] (* Michael De Vlieger, Dec 31 2016 *)

A264024 a(n) = gcd(phi(k), k-1) / lambda(k), where k is n-th Carmichael number A002997(n) and lambda(k) = A002322(k).

Original entry on oeis.org

1, 1, 12, 2, 1, 1, 9, 1, 4, 1, 6, 18, 1, 1, 1, 2, 1, 1, 1, 2, 12, 1, 1, 1, 1, 3, 3, 3, 50, 1, 18, 2, 1, 2, 1, 2, 5, 36, 1, 1, 2, 3, 4, 3, 3, 2, 3, 1, 1, 3, 3, 2, 4, 2, 5, 1, 4, 4, 4, 1, 1, 3, 40, 28, 1, 2, 4, 2, 4, 1, 2, 1, 2, 1, 33, 5, 50, 64, 1, 1, 3, 2, 1, 1, 12, 3, 1, 12, 1, 1, 1, 24, 1, 3, 128, 1, 6, 8, 5, 20, 3, 2, 2, 6, 4

Offset: 1

Thomas Ordowski, Nov 01 2015

nonn

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

Cf. A002322, A002997, A049559, A174590, A264012.

t = Cases[Range[1, 16 (10^6), 2], n_ /; Mod[n, CarmichaelLambda@ n] == 1 && ! PrimeQ@ n]; Table[GCD[EulerPhi@ t[[n]], t[[n]] - 1]/CarmichaelLambda@ t[[n]], {n, 105}] (* Michael De Vlieger, Nov 03 2015, after Artur Jasinski at A002997: alternatively use A002997 data for t *)

t(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1;
is(n)=n%2 && !isprime(n) && t(n) && n>1;
c(n)=gcd(eulerphi(n),n-1)/lcm(znstar(n)[2]);
for(n=1, 1e7, if(is(n), print1(c(n)", "))) \\ Altug Alkan, Nov 01 2015

a(n) = A049559(k)/A002322(k), where k = A002997(n).

More terms from Altug Alkan, Nov 01 2015

A283656 Numbers n such that gcd(phi(n), n-1) > lambda(n).

Original entry on oeis.org

65, 91, 217, 273, 451, 481, 703, 793, 1281, 1729, 1891, 1921, 2465, 2701, 3201, 4033, 4097, 4681, 5833, 6643, 6697, 7105, 7161, 8321, 8401, 8911, 9073, 10649, 11041, 11476, 11521, 12403, 12545, 13051, 14689, 14701, 15841, 16385, 16401, 16471, 18361, 18705, 18721, 19684, 19951, 20801, 21953, 22177, 22681, 23001

Offset: 1

Thomas Ordowski and Altug Alkan, Mar 23 2017

nonn

All terms are composite. No powers of primes.
Contains all Carmichael numbers except A264012.
If n is in the sequence, then n-1 is not squarefree.
Problem: are there infinitely many such even numbers? : 11476, 19684, 24564, 37576, 57226, 65026, 80476, 89776, 91356, ...
It is possible to show there are infinitely many Carmichael numbers with the property. In fact this follows with a small modification of the original proof of the infinitude of the Carmichael numbers. It seems harder though to prove that there are infinitely many non-Carmichaels with the property, though undoubtedly it's true. - Carl Pomerance, Mar 24 2017

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

Cf. A000010, A002322, A002997, A049559, A264012.

Select[Range[10^4], GCD[EulerPhi[#], #-1] > CarmichaelLambda[#] &] (* Amiram Eldar, Aug 26 2019 *)

A257643 Carmichael numbers k such that k-1 is squarefree.

Original entry on oeis.org

139952671, 74689102411, 121254376891, 187054437571, 231440115271, 236359158267, 303008129971, 306252926071, 380574791611, 426951670531, 556303918171, 639109148371, 660950414671, 1101375141511, 1483826843731, 1487491483171, 1861175569891, 2794268624071

Offset: 1

Thomas Ordowski, Nov 05 2015

nonn

If k is a Carmichael number with k-1 squarefree, then gcd(phi(k),k-1) = lambda(k), i.e., Carmichael lambda function A002322.

Amiram Eldar, Table of n, a(n) for n = 1..5287 (terms below 10^22, calculated using data from Claude Goutier; terms 1..164 from Robert Israel, terms 165..1037 from Charles R Greathouse IV)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.

Subsequence of A185321.

Cf. A002997, A264012, A007674.

t(n) = my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1;
is(n) = n%2 && !isprime(n) && t(n) && n>1;
isok(n) = is(n) && issquarefree(n-1); \\ Altug Alkan, Nov 06 2015

is(n) = my(f=factor(n)); for(i=1, #f~, if(f[i,1]%4<3 || f[i, 2]>1 || (n-1)%(f[i, 1]-1), return(0))); !isprime(n) && issquarefree(n-1)
is(n) = n%2 && !isprime(n) && t(n) && n>1 \\ Charles R Greathouse IV, Nov 09 2015

A283872 Numbers k such that gcd(phi(k), k-1) > lambda(k)^2.

Original entry on oeis.org

432046225, 631071001, 4579461601, 8494657921, 53282340865, 80601412609

Offset: 1

Thomas Ordowski and Altug Alkan, Mar 24 2017

2320690177 is the only 2 < k < 10^11 such that gcd(phi(k),k-1) = lambda(k)^2. - Giovanni Resta, Mar 24 2017

Cf. A000010, A002322, A049559, A264012, A283656.

a(3)-a(6) from Giovanni Resta, Mar 24 2017

A284406 Odd numbers k such that lambda(k) < phi(k) and gcd(lambda(k), k-1) = gcd(phi(k), k-1).

Original entry on oeis.org

15, 35, 39, 45, 51, 55, 63, 75, 85, 87, 95, 99, 111, 115, 117, 119, 123, 135, 143, 147, 153, 155, 159, 165, 171, 175, 183, 187, 195, 203, 205, 207, 215, 219, 221, 231, 235, 245, 247, 255, 259, 261, 267, 275, 279, 285, 287, 291, 295, 299, 303, 315, 319, 323, 325, 327, 333, 335, 339, 351

Offset: 1

Thomas Ordowski and Altug Alkan, Mar 26 2017

nonn

If odd n is in A033949 and n-1 is squarefree, then n is in the sequence.
The set of such numbers has a positive natural density.
The density is 1/2. Almost all odd numbers have this property.
The number of terms below 10^k for k = 1, 2, ... are 0, 12, 204, 2507, 27801, 296583, 3102205, 32054920, 328714616, 3353406273, .... Apparently the asymptotic density of this sequence is less than 1/2. - Amiram Eldar, Jul 14 2020

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..439 from Indranil Ghosh)

Subsequence of A257591.
A264012 is a subsequence.
Cf. A000010, A002322, A280262.

Select[Range[1, 351, 2], Function[k, And[#1 < #2, GCD[#1, k - 1] == GCD[#2, k - 1]] & @@ {CarmichaelLambda@ k, EulerPhi@ k}]] (* Michael De Vlieger, Mar 26 2017 *)

A290281 Numbers k such that (k-1) mod phi(k) = lambda(k), where phi = A000010 and lambda = A002322.

Original entry on oeis.org

6601, 11972017, 34657141, 67902031, 139952671, 258634741, 2000436751, 8801128801, 9116583841, 9462932431, 38069223721, 326170416001, 359316634951, 1860929324101, 2022188518351, 2283475947391, 2648686458601, 2697891108151, 4513362899761, 5020030521001, 5472940991761, 6163867710001, 7507903975951, 19288340548471

Offset: 1

Robert Israel and Thomas Ordowski, Jul 25 2017

nonn

Numbers k such that A215486(k) = A002322(k).
Subsequence of the Carmichael numbers (A002997).
Composite numbers k such that (k-1) == lambda(k) (mod phi(k)).
Composite numbers k such that A277127(k) == 1 (mod A000010(k)).
Problem: are there infinitely many such numbers?
Conjecture: these are numbers k such that phi(k) + lambda(k) = k - 1. Checked up to 2^64. - Amiram Eldar and Thomas Ordowski, Dec 06 2019

Amiram Eldar, Table of n, a(n) for n = 1..239 (terms below 10^22 calculated using data from Claude Goutier; terms 1..79 from Robert Israel)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Index entries for sequences related to Carmichael numbers.

Cf. A000010, A002322, A002997, A215486.

Subsequence of A264012.

# Using data files for A002997
count:= 0:
for cfile in ["carmichael-16","carmichael17","carmichael18"] do
do
    S:= readline(cfile);
    if S = 0 then break fi;
    L:= map(parse, StringTools:-Split(S));
    n:= L[1]; pm:= map(`-`,L[2..-1],1);
    phin:= convert(pm,`*`);
    lambdan:= ilcm(op(pm));
    if n-1 - lambdan mod phin = 0 then
      count:= count+1; A[count]:= n;
    fi
od:
   fclose(cfile);
od:
seq(A[i],i=1..count); # Robert Israel, Jul 26 2017

Select[Range[10^8], Divisible[# - 1, (lam = CarmichaelLambda[#])] && Mod[# - 1, EulerPhi[#]] == lam &] (* Amiram Eldar, Dec 06 2019 *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A280262 Numbers n such that A187730(n) < A049559(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A264024 a(n) = gcd(phi(k), k-1) / lambda(k), where k is n-th Carmichael number A002997(n) and lambda(k) = A002322(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A283656 Numbers n such that gcd(phi(n), n-1) > lambda(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A257643 Carmichael numbers k such that k-1 is squarefree.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

A283872 Numbers k such that gcd(phi(k), k-1) > lambda(k)^2.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A284406 Odd numbers k such that lambda(k) < phi(k) and gcd(lambda(k), k-1) = gcd(phi(k), k-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A290281 Numbers k such that (k-1) mod phi(k) = lambda(k), where phi = A000010 and lambda = A002322.

Views

Author

Keywords

Comments

Links

Crossrefs