A339817 -id:A339817 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

85, 561, 1105, 1261, 1285, 2465, 4369, 6601, 8245, 8481, 9061, 9605, 10585, 16405, 16705, 17733, 18721, 19669, 21845, 23001, 28645, 30889, 38165, 42121, 43165, 46657, 54741, 56797, 57205, 62745, 65365, 74593, 78013, 83665, 88561, 91001, 106141, 117181, 124645, 126701, 134521, 136981, 141661, 162401, 171205, 176437

Offset: 1

Antti Karttunen, Dec 22 2020

nonn

From Antti Karttunen, Dec 26 2020: (Start)
Equally, squarefree composite numbers k of the form 4u+1 for which A336466(k) divides k-1. This follows because on squarefree n, A336466(n) = A053575(n).
No common terms with A016105, because 4xy + 2(x+y) + 1 does not divide 4xy + 3(x+y) + 2 for any distinct x, y >= 0 (where 4x+3 and 4y+3 are the two prime factors of Blum integers).
This can also seen by another way: If this sequence contained any Blum integers, then, because A016105 is a subsequence of A339817, we would have found a composite number n satisfying Lehmer's totient problem y * phi(n) = n-1, for some integer y > 1. But Lehmer proved that such solutions should have at least 7 distinct prime factors, while Blum integers have only two.
Moreover, it seems that none of the terms of A167181 may occur here, and a few of A137409 (i.e., of A125667). See A339875 for those terms.
(End)

			85 = 4*21 + 1 = 5*17, thus phi(85) = 4*16 = 64, the odd part of which is A000265(64) = 1, which certainly divides 85-1, therefore 85 is included as a term.
561 = 4*140 + 1 = 3*11*17, thus phi(561) = 2*10*16 = 320, the odd part of which is A000265(320) = 5, which divides 560, therefore 561 is included.

Antti Karttunen, Table of n, a(n) for n = 1..1316
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, A000265, A016105, A053575, A137409, A167181, A336466.
Subsequence of A005117.
Intersection of A091113 and A339880.
Cf. A339875 (a subsequence).
Cf. also comments in A339817.

odd[n_] := n/2^IntegerExponent[n, 2]; Select[4*Range[45000] + 1, CompositeQ[#] && Divisible[# - 1, odd[EulerPhi[#]]] &] (* Amiram Eldar, Feb 17 2021 *)

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

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

A339816 Numbers k for which A339814(k) >= A339822(k).

Original entry on oeis.org

1, 2, 4, 5, 8, 9, 12, 14, 16, 18, 21, 32, 64, 65, 68, 72, 84, 128, 129, 132, 136, 138, 141, 145, 159, 170, 192, 204, 208, 256, 258, 261, 324, 385, 448, 462, 512, 513, 515, 516, 520, 536, 576, 578, 581, 640, 705, 723, 776, 908, 912, 1024, 1036, 1040, 1049, 1160, 1172, 1280, 1352, 1537, 1600, 1609, 1666, 1732, 1795, 2048

Offset: 1

Antti Karttunen, Dec 19 2020

nonn

Terms of (1/2)*A048675(A339817(i)), for i = 2.., sorted into ascending order.

First occurrences of terms with binary weight (A000120) w = 1..19 are at n=1, 4, 8, 23, 50, 25, 125, 136, 176, 502, 749, 1142, 791, 1882, 2913, 4327, 17979, 16991, 12441. The terms themselves are: 1, 5, 14, 141, 908, 159, 8921, 9948, 18390, 175449, 400237, 1223389, 441805, 3234271, 28743379, 53892047, 1631024969, 1331412056, 725475951.

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

Positions of zeros and negative terms in A339815.
Cf. A000010, A000120, A007814, A019565, A048675, A339814, A339817, A339822.
Cf. A000079 (a subsequence).

A019565(n) = { my(m=1, p=1); while(n>0, p = nextprime(1+p); if(n%2, m *= p); n >>= 1); (m); };
isA339816(n) = { my(x=A019565(2*n)); (valuation(eulerphi(x),2)<=valuation(x-1,2)); };

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

A339907 Odd squarefree numbers k > 1 for which the bigomega(phi(k)) <= bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 21 2020

nonn

Terms of A003961(A019565(A339906(i))) [or equally, of A019565(2*A339906(i))], for i = 1.., sorted into ascending order.

Natural numbers n > 2 that satisfy equation k * phi(n) = n - 1 (for some integer k) all occur in this sequence. Lehmer conjectured that there are no composite solutions.

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

Cf. A339906.
Cf. A065091, A339908 (subsequences).
Cf. also A339817.
Apart from initial 3, a subsequence of A339910.

isA339907(n) = ((n>1)&&(n%2)&&issquarefree(n)&&(bigomega(eulerphi(n))<=bigomega(n-1)));

A339819 Squarefree numbers k > 1 for which neither 2-adic nor 3-adic valuation of phi(k) exceeds the corresponding valuation of k-1.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 33, 37, 41, 43, 47, 53, 59, 61, 67, 69, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 141, 145, 149, 151, 157, 163, 167, 173, 177, 179, 181, 191, 193, 197, 199, 211, 213, 217, 223, 227, 229, 233, 239, 241, 249, 251, 253, 257, 263, 269, 271, 277, 281, 283

Offset: 1

Antti Karttunen, Dec 20 2020

nonn

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

Cf. A000010, A005117, A007814, A007949.

Subsequence of A339817.

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

A339871 Number of primes p for which the p-adic valuation of phi(n) exceeds the p-adic valuation of n-1, with a(1) = 0 by convention.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 2, 1, 1, 0, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 1, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 1, 0, 2, 0, 2, 2, 2, 0, 1, 1, 2, 1, 1, 0, 2, 2, 2, 1, 2, 0, 1, 0, 3, 2, 1, 1, 1, 0, 1, 1, 1, 0, 2, 0, 2, 2, 2, 2, 2, 0, 1, 1, 2, 0, 2, 1, 3, 2, 2, 0, 2, 1, 2, 2, 2, 2, 1, 0, 3, 3, 2, 0, 1, 0, 2, 2

Offset: 1

Antti Karttunen, Dec 20 2020

nonn

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

Cf. A001221, A055734, A160595, A339817, A339872.

A339871(n) = if(1==n,0,my(s=0); for(k=1,n,my(p=prime(k)); if(valuation(eulerphi(n),p)>valuation(n-1,p), s++)); (s));

A339871(n) = if(1==n,0,my(f=factor(eulerphi(n))); sum(i=1,#f~,f[i,2]>valuation(n-1,f[i,1])));

A339871(n) = omega(eulerphi(n)/gcd(n-1,eulerphi(n)));

a(n) = A001221(A160595(n)).

a(n) <= A055734(n).

A339872 Index k of the least prime(k) such that prime(k)-adic valuation of phi(n) exceeds the prime(k)-adic valuation of n-1, or 0 if no such k exists (for example, when n = 1 or a prime).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 2, 1, 0, 1, 3, 1, 2, 1, 0, 1, 0, 1, 3, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 4, 1, 1, 1, 0, 1, 1, 1, 2, 1, 0, 1, 0, 1, 1, 1, 2, 1, 0, 1, 5, 1, 0, 1, 0, 1, 1, 1, 2, 1, 0, 1, 2, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1

Offset: 1

Antti Karttunen, Dec 20 2020

nonn

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

Cf. A055396, A160595, A339817, A339871.

A339872(n) = if(1==n,0,for(k=1,n,my(p=prime(k)); if(valuation(eulerphi(n),p)>valuation(n-1,p), return(k))); (0));

A339872(n) = if(1==n,0,my(f=factor(eulerphi(n))); for(i=1,#f~,if(f[i,2]>valuation(n-1,f[i,1]), return(primepi(f[i,1])))); (0));

A339872(n) = { my(t=eulerphi(n), x=t/gcd(n-1,t)); if(1==x,0,primepi(factor(x)[1, 1])); };

a(n) = A055396(A160595(n)).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

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

A339816 Numbers k for which A339814(k) >= A339822(k).

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

A339907 Odd squarefree numbers k > 1 for which the bigomega(phi(k)) <= bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A339819 Squarefree numbers k > 1 for which neither 2-adic nor 3-adic valuation of phi(k) exceeds the corresponding valuation of k-1.

Views

Author

Keywords

Links

Crossrefs