A107978 -id:A107978 - 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

A080774 Numbers with two prime factors: (4i+1)(4*j+3).

Original entry on oeis.org

15, 35, 39, 51, 55, 87, 91, 95, 111, 115, 119, 123, 143, 155, 159, 183, 187, 203, 215, 219, 235, 247, 259, 267, 287, 291, 295, 299, 303, 319, 323, 327, 335, 339, 355, 371, 391, 395, 403, 407, 411, 415, 427, 447, 451, 471, 511, 515, 519, 527, 535, 543, 551

Offset: 1

Reinhard Zumkeller, Mar 10 2003

nonn

Semiprimes of the form 4k+3. - Giovanni Teofilatto, Jun 15 2005

There are 971 semiprimes of the form 4k+3 below 10,000.

			a(1) = 15 = 3*5 = (4*1+1)*(4*0+3).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Eric Weisstein's World of Mathematics, Semiprime.
Wikipedia, Semiprime.

Cf. A001358, A006881, A002144, A002145, A107978, A121387.

Select[Range[15, 1000, 2], Last /@ FactorInteger[#] == {1, 1} && IntegerQ[(# - 3)/4] &] (* Vladimir Joseph Stephan Orlovsky, May 07 2011 *)
Select[4*Range[200]+3,PrimeOmega[#]==2&] (* Harvey P. Dale, Nov 02 2024 *)

isok(k) = k % 4 == 3 && bigomega(k) == 2; \\ Amiram Eldar, Jun 15 2025

A057948 S-primes: let S = {1,5,9, ... 4i+1, ...}; then an S-prime is in S but is not divisible by any members of S except itself and 1.

Original entry on oeis.org

5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, 201, 209, 213, 217, 229, 233, 237, 241, 249, 253, 257, 269, 277, 281, 293, 301, 309, 313, 317, 321, 329

Offset: 1

Jud McCranie, Oct 14 2000

nonn

Factorization in S is not unique. See related sequences.
Kostrikin calls these numbers quasi-primes. - Arkadiusz Wesolowski, Aug 19 2017
a(n) is a prime of the form 4*n + 1 or a product of 2 primes of the form 4*n + 3. - David A. Corneth, Nov 10 2018

			21 is of the form 4i+1, but it is not divisible by any smaller S-primes, so 21 is in the sequence.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, page 101, problem 1.
A. I. Kostrikin, Introduction to Algebra, universitext, Springer, 1982.

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Hilbert Number [From _Eric W. Weisstein_, Sep 15 2008]

Union of A002144 and A107978. - Charlie Neder, Nov 03 2018

Cf. A054520, A057949, A057950.

N:= 1000: # to get all terms <= N
S:= {seq(4*i+1,i=1..floor((N-1)/4))}:
for n from 1 while n <= nops(S) do
  r:= S[n];
  S:= S minus {seq(i*r,i=2..floor(N/r))};
od:
S; # Robert Israel, Dec 14 2014

nn = 100; Complement[Table[4 k + 1, {k, 1, nn}], Union[Flatten[ Table[Table[(4 k + 1) (4 j + 1), {k, 1, j}], {j, 1, nn}]]]] (* Geoffrey Critzer, Dec 14 2014 *)

is(n) = if(n % 2 == 0, return(0)); if(n%4 == 1 && isprime(n), return(1)); f = factor(n); if(vecsum(f[, 2]) != 2, return(0)); for(i = 1, #f[, 1], if(f[i, 1] % 4 == 1, return(0))); n>1 \\ David A. Corneth, Nov 10 2018

a(n) ~ C n log n / log log n, where C > 2. - Thomas Ordowski, Sep 09 2012

Offset corrected by Charlie Neder, Nov 03 2018

A108181 Semiprimes of the form 4n + 1.

Original entry on oeis.org

9, 21, 25, 33, 49, 57, 65, 69, 77, 85, 93, 121, 129, 133, 141, 145, 161, 169, 177, 185, 201, 205, 209, 213, 217, 221, 237, 249, 253, 265, 289, 301, 305, 309, 321, 329, 341, 361, 365, 377, 381, 393, 413, 417, 437, 445, 453, 469, 473, 481, 485, 489, 493, 497

Offset: 1

Giovanni Teofilatto, Jun 14 2005

Either a(n)=(4*i+1)*(4*j+1) or a(n)=(4*i+3)*(4*j+3); - Reinhard Zumkeller, Jun 15 2005

A107978 is a subsequence. - Reinhard Zumkeller, Jun 15 2005

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
K. Ford, Jason Sneed, Chebyshev's Bias for products of two primes, Exper. Math. 19 (4) (2010) 385-398

Cf. A080774, A001358, A002144, A002145, A107978, A121387.

IsSemiprime:= func; [s: n in [2..150] | IsSemiprime(s) where s is 4*n + 1]; // Vincenzo Librandi, Sep 22 2012

Select[4Range[0, 150] + 1, PrimeOmega[#] == 2&] (* Vincenzo Librandi, Sep 22 2012 *)

Corrected and extended by Reinhard Zumkeller, Jun 15 2005

A121387 Semiprimes p*q with p and q primes of the form 4k+1 (A002144).

Original entry on oeis.org

25, 65, 85, 145, 169, 185, 205, 221, 265, 289, 305, 365, 377, 445, 481, 485, 493, 505, 533, 545, 565, 629, 685, 689, 697, 745, 785, 793, 841, 865, 901, 905, 949, 965, 985, 1037, 1073, 1145, 1157, 1165, 1189, 1205, 1241, 1261, 1285, 1313, 1345, 1369, 1385, 1405, 1417

Offset: 1

Alford Arnold, Jul 26 2006, corrected Jun 24 2007

p and q can be the same. [Harvey P. Dale, Jan 15 2012]

The terms are semiprimes of the form 4k + 1, and comprise only a portion of all such semiprimes, see A108181. - Richard R. Forberg, Aug 27 2013

			65 = 5 * 13. Note that 5 mod 4 = 1 and 13 mod 4 = 1, so 65 is a term.

François Huppé, Table of n, a(n) for n = 1..10000 (First 1000 terms from T. D. Noe).

Cf. A001358, A002144.
Fifth row of A121388.
Union of A080109 and A131574.
Cf. A107978, A080774, A108181.

With[{prs=Select[Prime[Range[150]],Mod[#,4]==1&]},Take[Union[Times @@@ Tuples[prs,2]],60]] (* Harvey P. Dale, Jan 15 2012 *)

Better definition from T. D. Noe, Sep 25 2007

A176258 Numbers of the form 4k+1 with greatest prime divisor of the form 4m-1.

Original entry on oeis.org

9, 21, 33, 49, 57, 69, 77, 81, 93, 105, 121, 129, 133, 141, 161, 165, 177, 189, 201, 209, 213, 217, 237, 245, 249, 253, 285, 297, 301, 309, 321, 329, 341, 345, 361, 381, 385, 393, 413, 417, 437, 441, 453, 465, 469, 473, 489, 497, 501, 513, 517, 525, 529, 537, 553, 573

Offset: 1

Vladimir Shevelev, Apr 13 2010

nonn

All terms of A107978 are in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A176257, A176256, A176255, A107978, A002148, A002145, A016813, A004767.

Select[4 Range@ 150 + 1, Mod[#, 4] == 3 &[FactorInteger[#][[-1, 1]]] &] (* Michael De Vlieger, Feb 07 2016 *)

isok(n) = (n != 1) && ((n % 4) == 1) && ((vecmax(factor(n)[,1]) % 4) == 3); \\ Michel Marcus, Feb 07 2016

Corrected and extended by Michel Marcus, Feb 07 2016

A121388 Table read by antidiagonals which classifies the proper odd numbers by form (i,j) where i and j are the number of prime factors of the form 4k-1 and 4k+1 respectively.

Original entry on oeis.org

3, 5, 7, 9, 13, 11, 15, 21, 17, 19, 25, 35, 33, 29, 23, 27, 65, 39, 49, 37, 31, 45, 63, 85, 51, 57, 41, 43, 75, 105, 99, 145, 55, 69, 53, 47, 125, 175, 117, 147, 169, 87, 77, 61, 59, 81, 325, 195, 153, 171, 185, 91, 93, 73, 67, 135, 189, 425, 255, 165, 207, 205, 95, 121, 89

Offset: 1

Alford Arnold, Jul 26 2006

			Table begins:
Row(i,j)
1: (1,0) 3,7,11,19,23,31,43,47,59,67,71,79,83,103,... (A002145)
2: (0,1) 5,13,17,29,37,41,53,61,73,89,97,101,109,... (A002144)
3: (2,0) 9,21,33,49,57,69,77,93,121,129,133,141,... (A107978)
4: (1,1) 15,35,39,51,55,87,91,95,111,115,119,... (A080774)
5: (0,2) 25,65,85,145,169,185,205,221,265,289,... (A121387)
6: (3,0) 27,63,99,147,171,207,231,279,343,...
7: (2,1) 45,105,117,153,165,245,261,273,...
8: (1,2) 75,175,195,255,275,435,455,...
9: (0,3) 125,325,425,725,845,925,...
10:(4,0) 81,189,297,441,513,...
11:(3,1) 135,315,351,459,...
12:(2,2) 225,525,585,...
13:(1,3) 375,875,...
14:(0,4) 625,...

Cf. A120027. Subsequences begin A002145 A002144 A107978 A080774 A121387.

Edited, corrected and extended by Ray Chandler, Aug 08 2010

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

A080774 Numbers with two prime factors: (4*i+1)*(4*j+3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A057948 S-primes: let S = {1,5,9, ... 4i+1, ...}; then an S-prime is in S but is not divisible by any members of S except itself and 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A108181 Semiprimes of the form 4n + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Extensions

A121387 Semiprimes p*q with p and q primes of the form 4k+1 (A002144).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A176258 Numbers of the form 4k+1 with greatest prime divisor of the form 4m-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A121388 Table read by antidiagonals which classifies the proper odd numbers by form (i,j) where i and j are the number of prime factors of the form 4k-1 and 4k+1 respectively.

Views

A080774 Numbers with two prime factors: (4i+1)(4*j+3).