A339818 -id:A339818 - cp's OEIS frontend

A339817 Squarefree numbers k > 1 for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.

2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31, 33, 37, 41, 43, 47, 53, 57, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 89, 93, 97, 101, 103, 107, 109, 113, 127, 129, 131, 133, 137, 139, 141, 145, 149, 151, 157, 161, 163, 167, 173, 177, 179, 181, 191, 193, 197, 199, 201, 209, 211, 213, 217, 223, 227, 229, 233, 237, 239, 241

Offset: 1

Antti Karttunen, Dec 19 2020

nonn

After 2, terms of A003961(A019565(A339816(i))) [or equally, of A019565(2*A339816(i))], for i = 1.., sorted into ascending order.
Natural numbers n that satisfy equation y * phi(n) = n - 1 (with y an integer) all occur in this sequence. Lehmer conjectured that there are no solutions such that n is composite (and thus y > 1).
From Antti Karttunen, Dec 22-26 2020: (Start)
Composite terms in this sequence are all of the form 4u+1 (A016813, A091113).
Generally, if any term k > 2 here has x prime divisors (which are all odd and distinct, i.e., A001221(k) = A001222(k) = x), then k is of the form 2^x * u + 1 (where u maybe even or odd), because each prime divisor of k contributes at least one instance of 2 in phi(k). Specifically, each prime factor of the form 4u+3 (A002145) contributes one instance of 2 (+1 to the 2-adic valuation), while primes of the form 4u+1 (A002144) contribute at least +2 to the 2-adic valuation. There must be an even number of 4u+3 primes, as otherwise the product would be of the form 4u+3. On the other hand, although all the terms of A016105 occur here, none of them occurs in A339870.
If the only terms this sequence shares with A339879 are the primes (A000040), then Lehmer's conjecture certainly holds. Similarly if the sequences A339818 and A339869 do not have any common terms.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..21695
D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
Wikipedia, Lehmer's totient problem.

Cf. A000010, A002144, A002145, A007814, A016105, A016813, A091113, A339816.
Cf. A000040, A016105, A339818, A339819 (subsequences).
Cf. also A339879, A339907, A339869, A339870, A339880.

Select[Range[2, 250], SquareFreeQ[#] && IntegerExponent[EulerPhi[#], 2] <= IntegerExponent[# - 1, 2] &] (* Amiram Eldar, Feb 17 2021 *)

isA339817(n) = ((n>1)&&issquarefree(n)&&(valuation(eulerphi(n),2)<=valuation(n-1,2)));

A339869 Carmichael numbers k for which A053575(k) [the odd part of phi] divides k-1.

Original entry on oeis.org

561, 1105, 2465, 6601, 8911, 10585, 46657, 62745, 162401, 410041, 449065, 5148001, 5632705, 6313681, 6840001, 7207201, 11119105, 11921001, 19683001, 21584305, 26719701, 41298985, 55462177, 64774081, 67371265, 79411201, 83966401, 87318001, 99861985, 100427041, 172290241, 189941761, 484662529, 790623289, 809883361

Offset: 1

Antti Karttunen, Dec 22 2020

nonn

Lehmer conjectured that the equation k * phi(n) = n - 1 (with k integer) has no solutions for any composite n (i.e., when k > 1). If this sequence has no common terms with A339818, then the conjecture certainly holds.

Amiram Eldar, Table of n, a(n) for n = 1..1150 (terms below 10^22 calculated using data from Claude Goutier)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
Wikipedia, Lehmer's totient problem.
Index entries for sequences related to Carmichael numbers.

Intersection of A002997 and A339880.
Complement of A340092 in A002997.
Cf. A000010, A000265, A002322, A053575.
Cf. also A339818, A339878, A339909.

carmichaels = Cases[Import["https://oeis.org/A002997/b002997.txt", "Table"], {, }][[;; , 2]]; oddPart[n_] := n/2^IntegerExponent[n, 2]; q[n_] := Divisible[n - 1, oddPart[EulerPhi[n]]]; Select[carmichaels, q] (* Amiram Eldar, Dec 26 2020 *)

A000265(n) = (n>>valuation(n, 2));
A002322(n) = lcm(znstar(n)[2]);
isA339869(n) = ((n>1)&&!isprime(n)&&(!((n-1)%A002322(n)))&&!((n-1)%A000265(eulerphi(n))));

A339909 Carmichael numbers k for which bigomega(phi(k)) < bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

Original entry on oeis.org

1729, 14676481, 84350561, 90698401, 279377281, 382536001, 413138881, 542497201, 702683101, 781347841, 851703301, 939947009, 955134181, 3480174001, 4765950001, 5255104513, 5781222721, 5985964801, 7558388641, 7816642561, 8714965001, 9237473281, 13630072501, 18189007201, 21669076801, 21863001601, 23915494401, 25477682491

Offset: 1

Antti Karttunen, Dec 22 2020

nonn

Natural numbers n that satisfy equation k * phi(n) = n - 1, for some integer k > 1, should all occur in this sequence, if they exist at all. Lehmer conjectured that there are no such numbers.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (calculated using data from Claude Goutier)
Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
Wikipedia, Lehmer's totient problem.
Index entries for sequences related to Carmichael numbers.

Intersection of A002997 and A339908.
Cf. A000010, A001222, A002322.
Cf. also A339818, A339869, A339878.

carmichaels = Cases[Import["https://oeis.org/A002997/b002997.txt", "Table"], {, }][[;; , 2]]; Select[carmichaels, PrimeOmega[EulerPhi[#]] < PrimeOmega[# - 1] &] (* Amiram Eldar, Dec 26 2020 *)

A002322(n) = lcm(znstar(n)[2]); \\ From A002322
isA339909(n) = ((n>1)&&issquarefree(n)&&!isprime(n)&&(bigomega(eulerphi(n))A002322(n))));

A339878 Carmichael numbers k such that phi(k) divides p*(k - 1) for some prime factor p of k - 1.

Original entry on oeis.org

1729, 3069196417, 23915494401, 1334063001601, 6767608320001, 33812972024833, 1584348087168001, 1602991137369601, 6166793784729601, 1531757211193440001, 84388996672599528001

Offset: 1

Antti Karttunen (after Thomas Ordowski's and Amiram Eldar's SeqFan-posting), Dec 26 2020

The first ten terms are all in A339818, none is in A339869, and all except a(2) and a(6) are in A339909.

Also, for all ten, a(n) == 1 (mod 64). (Cf. a similar comment in A338998).

Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
Thomas Ordowski and Amiram Eldar, A new look at the Lehmer's totient problem, SeqFan, February 10 2019.

Intersection of A002997 and A338998.

Cf. also A339818, A339869, A339909.

carmichaels = Cases[Import["https://oeis.org/A002997/b002997.txt", "Table"], {, }][[;; , 2]]; q[n_] := Module[{p = FactorInteger[n - 1][[;; , 1]], phi = EulerPhi[n]}, AnyTrue[(n - 1)*p, Divisible[#, phi] &]]; Select[carmichaels, q] (* Amiram Eldar, Dec 26 2020 *)

a(10) from Amiram Eldar, Dec 26 2020

a(11) calculated using data from Claude Goutier and added by Amiram Eldar, Apr 21 2024

cp's OEIS Frontend

A339817 Squarefree numbers k > 1 for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A339869 Carmichael numbers k for which A053575(k) [the odd part of phi] divides k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A339909 Carmichael numbers k for which bigomega(phi(k)) < bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A339878 Carmichael numbers k such that phi(k) divides p*(k - 1) for some prime factor p of k - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions