A339870 -id:A339870 - cp's OEIS frontend

A339875 Intersection of A137409 and A339870: Composite numbers k of the form 4u+1 having more than one prime factor of type 4u+3, and for which the odd part of phi(k) divides k-1.

561, 6601, 8481, 17733, 23001, 30889, 54741, 62745, 88561, 106141, 319965, 359601, 449065, 534061, 609301, 949785, 1357621, 2162721, 2288661, 2615977, 3284281, 4005001, 4698001, 4830805, 5381265, 6313681, 6594721, 6840001, 8093701, 11782005, 11921001, 14665105, 14892153, 15217741, 16577785, 19683001, 20154061, 20441701

Offset: 1

Antti Karttunen, Dec 26 2020

nonn

Composite numbers k of the form 4u+1 for which the odd part of phi(k) divides k-1 and for which A065338(k) > 1.

All terms k are squarefree and the 3-adic valuation of A065338(k) is a nonzero even number.

Intersection of A137409 and A339870.

Cf. A000010, A000265, A053575, A065338.

A065338(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = (f[i, 1]%4)); factorback(f); };
isA137409(n) = ((1==n)||(A065338(n)>1)); \\ Antti Karttunen, Dec 26 2020
A000265(n) = (n>>valuation(n, 2));
isA339870(n) = ((n>1)&&!isprime(n)&&(1==(n%4))&&!((n-1)%A000265(eulerphi(n))));
isA339875(n) = (isA137409(n)&&isA339870(n));

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 3, 1, 1, 1, 1, 9, 1, 3, 5, 11, 1, 1, 3, 1, 3, 7, 1, 15, 1, 5, 1, 3, 1, 9, 9, 3, 1, 5, 3, 21, 5, 1, 11, 23, 1, 9, 1, 1, 3, 13, 1, 5, 3, 9, 7, 29, 1, 15, 15, 3, 1, 3, 5, 33, 1, 11, 3, 35, 1, 9, 9, 1, 9, 15, 3, 39, 1, 1, 5, 41, 3, 1, 21, 7, 5, 11, 1, 9, 11, 15, 23, 9, 1, 3, 9, 5, 1, 25, 1, 51, 3, 3

Offset: 1

Antti Karttunen, Jul 22 2020

For the comment here, we extend the definition of the second kind of Cunningham chain (see Wikipedia-article) so that also isolated primes for which neither (p+1)/2 nor 2p-1 is a prime are considered to be in singular chains, that is, in chains of the length one. If we replace one or more instances of any particular odd prime factor p in n with any odd prime q in such a chain, so that m = (q^k)*n / p^(e-k), where e is the exponent of p of n, and k <= e is the number of instances of p replaced with q, then it holds that a(m) = a(n), and by induction, the value stays invariant for any number of such replacements. Note also that A001222, but not necessarily A001221 will stay invariant in such changes.
For example, if some of the odd prime divisors p of n are in A005382, then replacing it with 2p-1 (i.e., the corresponding terms of A005383), gives a new number m, for which a(m) = a(n). And vice versa, the same is true for any of the prime divisors > 3 of n that are in A005383, then replacing any one of them with (p+1)/2 will not affect the result. For example, a(37*37*37) = a(19*37*73) = 729 as 37 is both in A005382 and in A005383.
a(n) = A053575(n) for squarefree n (A005117). - Antti Karttunen, Mar 16 2021

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Wikipedia, Cunningham chain

Cf. A000265, A003958, A005117, A005382, A005383, A053575, A329697, A333787, A335915, A336396, A336467, A336468, A339870, A339876 [= a(A122111(n))], A339903 [= a(A003961(n))], A340084 [= gcd(n-1, a(n))], A340085, A340086.

Cf. also A336460, A336470, A339974.

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

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

a(n) = A000265(A003958(n)) = A000265(A333787(n)).
a(A000010(n)) = A336468(n) = a(A053575(n)).
A329697(a(n)) = A336396(n) = A329697(n) - A087436(n).
a(n) = A335915(n) / A336467(n). - Antti Karttunen, Mar 16 2021

A016105 Blum integers: numbers of the form p * q where p and q are distinct primes congruent to 3 (mod 4).

Original entry on oeis.org

21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, 501, 517, 537, 553, 573, 581, 589, 597, 633, 649, 669, 681, 713, 717, 721, 737, 749, 753, 781, 789

Offset: 1

Robert G. Wilson v

Subsequence of A084109. - Ralf Stephan and David W. Wilson, Apr 17 2005
Subsequence of A046388. - Altug Alkan, Dec 10 2015
Subsequence of A339817. No common terms with A339870. - Antti Karttunen, Dec 26 2020
Named after the Venezuelan-American computer scientist Manuel Blum (b. 1938). - Amiram Eldar, Jun 06 2021
First introduced by Blum, Blum, & Shub for the generation of pseudorandom numbers and later applied (by Manuel Blum and other authors) to zero-knowledge proofs. - Charles R Greathouse IV, Sep 26 2024

Lenore Blum, Manuel Blum, and Mike Shub. A simple unpredictable pseudorandom number generator, SIAM Journal on computing 15:2 (1986), pp. 364-383.

Antti Karttunen, Table of n, a(n) for n = 1..26828 (all terms < 2^19; first 1000 terms from T. D. Noe)
Joe Hurd, Blum Integers, Talk at the Trinity College, Jan 20 1997.
Wikipedia, Blum integer.

Cf. A002145, A006881, A046388, A339870.
Intersection of A005117 and A107978.
Also, subsequence of the following sequences: A046388, A084109, A091113, A167181, A339817.

import Data.Set (singleton, fromList, deleteFindMin, union)
a016105 n = a016105_list !! (n-1)
a016105_list = f [3,7] (drop 2 a002145_list) 21 (singleton 21) where
   f qs (p:p':ps) t s
     | m < t     = m : f qs (p:p':ps) t s'
     | otherwise = m : f (p:qs) (p':ps) t' (s' `union` (fromList pqs))
     where (m,s') = deleteFindMin s
           t' = head $ dropWhile (> 3*p') pqs
           pqs = map (p *) qs
-- Reinhard Zumkeller, Sep 23 2011

N:= 10000: # to get all terms <= N
Primes:= select(isprime, [seq(i,i=3..N/3,4)]):
S:=select(`<=`,{seq(seq(Primes[i]*Primes[j],i=1..j-1),j=2..nops(Primes))},N):
sort(convert(S,list)); # Robert Israel, Dec 11 2015

With[{upto = 820}, Select[Union[Times@@@Subsets[ Select[Prime[Range[ PrimePi[ NextPrime[upto/3]]]], Mod[#, 4] == 3 &], {2}]], # <= upto &]] (* Harvey P. Dale, Aug 19 2011 *)
Select[4Range[5, 197] + 1, PrimeNu[#] == 2 && MoebiusMu[#] == 1 && Mod[FactorInteger[#][[1, 1]], 4] != 1 &] (* Alonso del Arte, Nov 18 2015 *)

list(lim)=my(P=List(),v=List(),t,p); forprimestep(p=3,lim\3,4, listput(P,p)); for(i=2,#P, p=P[i]; for(j=1,i-1, t=p*P[j]; if(t>lim, break); listput(v,t))); Set(v) \\ Charles R Greathouse IV, Jul 01 2016, updated Sep 26 2024

isA016105(n) = (2==omega(n)&&2==bigomega(n)&&1==(n%4)&&3==((factor(n)[1,1])%4)); \\ Antti Karttunen, Dec 26 2020

use ntheory ":all"; forcomposites { say if ($ % 4) == 1 && is_square_free($) && scalar(factor($)) == 2 && !scalar(grep { ($ % 4) != 3 } factor($)); } 10000; # _Dana Jacobsen, Dec 10 2015

from sympy import factorint
def ok(n):
    fn = factorint(n)
    return len(fn) == sum(fn.values()) == 2 and all(f%4 == 3 for f in fn)
print([k for k in range(790) if ok(k)]) # Michael S. Branicky, Dec 20 2021

a(n) = A195758(n) * A195759(n). - Reinhard Zumkeller, Sep 23 2011

a(n) ~ 4n log n/log log n. - Charles R Greathouse IV, Sep 17 2022

More terms from Erich Friedman

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

Original entry on oeis.org

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))));

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)));

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.

cp's OEIS Frontend

A339875 Intersection of A137409 and A339870: Composite numbers k of the form 4u+1 having more than one prime factor of type 4u+3, and for which the odd part of phi(k) divides k-1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A016105 Blum integers: numbers of the form p * q where p and q are distinct primes congruent to 3 (mod 4).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Perl

Python

Formula

Extensions

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

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

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