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

Author

Robert G. Wilson v

Keywords

• nonn
• easy
• nice

Comments

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

References

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

Links

• 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.

Crossrefs

Cf. A002145, A006881, A046388, A339870.

Intersection of A005117 and A107978.

Also, subsequence of the following sequences: A046388, A084109, A091113, A167181, A339817.

Programs

Haskell

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

Maple

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

Mathematica

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

PARI

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

PARI

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

Perl

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

Python

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

Formula

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

Extensions

More terms from Erich Friedman