A339869 -id:A339869 - 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)));

A339880 Odd composite numbers k such that A053575(k) [the odd part of phi] divides k-1.

Original entry on oeis.org

15, 51, 85, 91, 255, 435, 451, 561, 595, 771, 1105, 1261, 1285, 1351, 1695, 2091, 2431, 2465, 3655, 3855, 4369, 4795, 5083, 5151, 5383, 6601, 6643, 6735, 7051, 8245, 8481, 8695, 8911, 8995, 9061, 9605, 10585, 11155, 13107, 15051, 15211, 16405, 16705, 17733, 18721, 19669, 20451, 21845, 22359, 23001, 26335, 28645

Offset: 1

Antti Karttunen, Dec 24 2020

nonn

No common terms with A016105. See A339870 for the reason. - Antti Karttunen, Dec 26 2020

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

Cf. A000010, A000265, A016105, A053575.
Subsequence of A005117 and of A339879, and of A340077.
Cf. A339869, A339870 (subsequences).
Cf. also A002997, A053576, A339817.

A000265(n) = (n>>valuation(n, 2));
isA339880(n) = (bitand(n,1)&&(n>1)&&!isprime(n)&&!((n-1)%A000265(eulerphi(n))));

A339818 Carmichael numbers k for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.

Original entry on oeis.org

1729, 15841, 3057601, 3828001, 5310721, 8355841, 8830801, 9439201, 14676481, 15829633, 17236801, 40280065, 78091201, 83099521, 84350561, 92625121, 94536001, 104852881, 118901521, 129762001, 157731841, 163954561, 180115489, 193708801, 214852609, 221884001, 279377281, 382304161, 382536001, 438359041, 481239361, 511338241

Offset: 1

Antti Karttunen, Dec 20 2020

nonn

Amiram Eldar, Table of n, a(n) for n = 1..22784 (terms below 2^64)

Intersection of A002997 and A339817 (see comments in latter).

Cf. also A339869, A339878, A339909.

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

A002322(n) = lcm(znstar(n)[2]); \\ From A002322
isA339818(n) = ((n>1)&&issquarefree(n)&&!isprime(n)&&(valuation(eulerphi(n),2)<=valuation(n-1,2))&&(0==((n-1)%A002322(n))));

A339879 Numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 19, 20, 23, 24, 28, 29, 30, 31, 32, 34, 37, 40, 41, 43, 47, 48, 51, 52, 53, 59, 60, 61, 64, 66, 67, 68, 70, 71, 73, 79, 80, 83, 85, 89, 91, 96, 97, 101, 102, 103, 107, 109, 112, 113, 120, 127, 128, 130, 131, 136, 137, 139, 149, 151, 157, 160, 163, 167, 170, 173, 176, 179

Offset: 1

Antti Karttunen, Dec 24 2020

nonn

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

Cf. A000010, A000265, A053575.
Subsequences: A000040, and A339880 (odd composite terms), A339869, A339870.
Cf. also comments in A339817.

A000265(n) = (n>>valuation(n, 2));
isA339879(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

A340077 Odd numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].

Original entry on oeis.org

1, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71, 73, 79, 83, 85, 89, 91, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 255, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313

Offset: 1

Antti Karttunen, Dec 29 2020

nonn

Sequence A003961(A340076(i)), i = 1.., sorted into ascending order. In other words, this sequence consists of such odd numbers k that A064989(k) is in A340076.

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

Cf. A064989, A340075, A340076.
Subsequence of A339879.
Subsequences: A065091, A339880 (composite terms), A339869, A339870 (and their further subsequences).

A000265(n) = (n>>valuation(n, 2));
isA340077(n) = ((n%2)&&!((n-1)%A000265(eulerphi(n))));

A064989(n) = { my(f=factor(n)); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f) };
isA340077(n) = ((n%2)&&(1==A340075(A064989(n)))); \\ Needs also code from A340075.

A339974 Odd primes that do not occur as the greatest prime divisor of any such odd composite k for which the odd part of phi(k) divides k-1.

Original entry on oeis.org

3, 7, 11, 19, 31, 37, 59, 61, 83, 103, 107, 131

Offset: 1

Antti Karttunen, Dec 27 2020

Odd primes that do not occur as the greatest prime divisor (A006530) of any of the terms of A339880.
Naive way of computing (essentially an exhaustive search): apply A000523 to the terms of A339973, select unique values, add +2, and take the corresponding prime.
Questions: Is this sequence finite? If infinite, are there still only a finite number of 4k+1 primes (A002144) like 37 and 61?
a(13) >= 149, if it exists.

			Prime 127 is NOT a member, because there exists a squarefree composite number 10697881195 = 5*29*53*97*113*127, for which A053575(10697881195) = A336466(10697881195) = 120393, which is a divisor of 10697881195-1. Note that 10697881195 is a term of A339880, but not that of A339870.

Cf. A000523, A002144, A006530, A053575, A336466, A339870, A339880, A339973.

Cf. also A339869.

A340091 Odd numbers k such that A064989(k) is in A340151.

Original entry on oeis.org

679, 703, 1387, 1729, 1891, 2047, 2509, 2701, 2821, 3277, 3367, 5551, 7471, 7735, 8119, 8827, 9997, 10963, 11305, 12403, 13021, 13747, 13981, 14491, 14701, 15841, 16471, 17563, 19951, 21349, 21907, 21931, 22015, 23959, 24727, 25669, 26281, 27511, 28939, 29341, 31417, 32407, 38503, 39091, 39831, 39865, 40501, 41041

Offset: 1

Antti Karttunen, Dec 31 2020

nonn

Sequence A003961(A340151(i)), for i >= 1, sorted into ascending order.

By definition, this has no common terms with A340077 nor any of its subsequences like A339869 or A339880.

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

Cf. A002997, A003961, A339869, A339880, A340077, A340151.

Cf. A340092 (Carmichael numbers in this sequence).

A000265(n) = (n>>valuation(n,2));
A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A339904(n) = A000265(eulerphi(A003961(n)));
A340075(n) = { my(u=A339904(n)); u/gcd(A003961(n)-1, u); };
A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
A340149(n) = A000265(A247074(A003961(n)));
isA340151(n) = ((1!=A340075(n))&&(1==A340149(n)));
A064989(n) = { my(f=factor(n)); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f) };
isA340091(n) = ((n%2)&&isA340151(A064989(n)));

A340092 Carmichael numbers k for which A053575(k) [the odd part of phi] does not divide k-1.

Original entry on oeis.org

1729, 2821, 15841, 29341, 41041, 52633, 63973, 75361, 101101, 115921, 126217, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633, 1024651, 1033669, 1050985, 1082809, 1152271, 1193221, 1461241, 1569457

Offset: 1

Antti Karttunen, Dec 31 2020

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Index entries for sequences related to Carmichael numbers.

Complement of A339869 in A002997.
Subsequence of A340091.
Cf. A002322, A053575.

odd[n_] := n/2^IntegerExponent[n, 2]; Select[Range[1, 10^6, 2], CompositeQ[#] && Divisible[# - 1, CarmichaelLambda[#]] && !Divisible[# - 1, odd @ EulerPhi[#]] &] (* Amiram Eldar, Dec 31 2020 *)

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

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

A339880 Odd composite numbers k such that A053575(k) [the odd part of phi] divides k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A339818 Carmichael numbers k for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A339879 Numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].

Views

Author

Keywords

Links

Crossrefs

Programs

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

A340077 Odd numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

A339974 Odd primes that do not occur as the greatest prime divisor of any such odd composite k for which the odd part of phi(k) divides k-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A340091 Odd numbers k such that A064989(k) is in A340151.

Views

Author

Keywords

Comments

Links