Outputting Blum Integers

Question

According to Wikipedia,

In mathematics, a natural number \$n\$ is a Blum integer if \$n = p \times q\$ is a semiprime for which \$p\$ and \$q\$ are distinct prime numbers congruent to \$3 \bmod 4\$. That is, \$p\$ and \$q\$ must be of the form \$4t + 3\$, for some integer \$t\$. Integers of this form are referred to as Blum primes. This means that the factors of a Blum integer are Gaussian primes with no imaginary part.

The first few Blum integers are:

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

This is OEIS A016105

Your task is to make a program that does one of the following:

• Take an index \$n\$ and output the \$n^{th}\$ Blum integer, either 0 or 1 indexing.
• Take a positive integer \$n\$ and output the first \$n\$ Blum integers.
• Output all Blum integers infinitely.

This is code-golf so shortest answer wins.

Answer 1

Python 3, 65 bytes

n=1
while[[d%4for d in range(2,n)if n%d<1]==[3,3]!=print(n)]:n+=4

Try it online!

Prints indefinitely. Identifies Blum integers as those with exactly two proper factors, both of which are 3 mod 4.

Answer 2

Jelly, 10 bytes

ÆḌ%4Ḅ⁼13µ#

A full program accepting an integer, \$n\$, from STDIN, that prints a list of the first \$n\$ Blum integers.

Try it online!

How?

First, note that a semi-prime has exactly three proper divisors: \$(1, p, q)\$, thus Blum integers may be identified by having \$X=(1\mod 4, p\mod 4, q\mod 4)\$ equal to \$(1,3,3)\$.

Next, note that if we treat \$X\$ as a binary number then Blum integers all evaluate to:
\$2^2\cdot 1 + 2^1\cdot 3 + 2^0\cdot 3=13\$

Next, note that the only way to have a string of \$[0..3]\$ evaluate as \$13\$ this way is to have either three or four proper divisors. Two is too few since \$2^1\cdot 3+2^0\cdot 3<13\$ and five is too many since \$2^4\cdot 1>13\$ and the smallest proper divisor is always \$1\$.

Lastly, note that the only numbers with exactly four proper divisors are fourth powers of primes, with proper divisors of \$(1, p, p^2, p^3)\$. Since \$p\mod 4\$ is never zero \$(1, 0, 1, 3)\$ and \$(1, 0, 2, 1)\$ cannot happen, so the only possible false positive that could exist after taking modulo four would be \$(1, 1, 0, 1)\$, but if \$p\equiv 1\pmod 4\$ then \$p^2\equiv 1\pmod 4\$, so that cannot happen either.

ÆḌ%4Ḅ⁼13µ# - Main Link: no arguments
        µ# - read n from STDIN, count up from k=0
             finding the first n k for which this f(k) is truthy:
ÆḌ         -   proper divisors
  %4       -   mod four
    Ḅ      -   convert from binary
     ⁼13   -   equals 13?

Answer 3

J, 32 bytes

(>:[]echo~~:/@q:*3 3-:4|q:)^:_@3

Try it online!

Outputs all Blum primes.

• ^:_@3 Starting with 3, and continuing to a fixed point (which will never be reached)...
• ]echo~~:/@q:*3 3-:4|q: If the the current number n's prime factors mod 4 exactly matches 3 3, and the numbers are not equal ~:/@q:*, then echo n as a side effect...
• >:[ Return n+1 for the next iteration.

Answer 4

Vyxal, 13 bytes

∞››'Ǐ'›4Ḋ;÷*=

Try it Online!

Prints infinitely.

∞››           # Positive integers (except 1)
   '          # Filtered by
    Ǐ         # Prime factors
     '   ;    # Filtered by
      ›       # Incremented 
       4Ḋ     # Is divisible by 4?
          ÷   # Push all to the stack separately
           *  # Product of the top two
            = # Is equal to (implicit input / another factor)

Let's go through the outcomes after ÷.

Case 1: 1 factor left. This gets multiplied by the original number, and since it's not 1, it can never equal the original number.

Case 2: 2 factors left. These two get multiplied together, and if it's the same as the original, it will be outputted.

Case 3: 3+ factors left. The top two will be multiplied, but can't equal the third because it's a prime.

Answer 5

05AB1E, 14 13 bytes

-1 byte thanks to Adnan!

Prints the infinite list of Blum numbers.

∞ʒfʒ4%Í}ü*θyQ

Try it online!

∞                 # infinite list of positive integers [1,2,...
 ʒ                # filter, keep y if
  f               #   push list of unique prime factors
   ʒ4%Í}          #   keep those where k%4-2==1
        ü*        #   get the products of all adjacent factors
          θ       #   take the last one (or the empty list if there are none)
           yQ     #   is this equal to y?

Answer 6

R, 61 56 bytes

-5 bytes thanks to @Dominic

while(T<-T+1)if(all(which(!T%%2:T)%%4==c(2,2,0)))show(T)

Try it online!

Outputs all Blum integers infinitely.

Explanation

As R doesn't have build-ins for prime factorisation we have to circumvent this.

Let's notice that:

• Blum integer needs to have exactly three non-trivial factors (prime or not) - including the number itself;
• The remainders \$ mod\ 4 \$ need to be \$3,3,1\$ respecitvely.

Therefore it suffices to check if the divisors of the number (which(!T%%2:T) is off-by-one) are all equal \$ mod\ 4 \$ to vector [3 3 1] (c(2,2,0) correcting the off-by-one).

^{Actually we could skip testing the number itself for mod4, but, you know, bytes...}

Answer 7

Retina, 78 bytes

\d*$
_
"$&"}/(^_|\1__)+$|^(__(___?)?(____)*)\2+$|^(?!(___(____)*)\5+$)/+`$
_
_

Try it online! Link includes test cases. Outputs the nth term. Explanation:

"$&"}`

Repeat n times.

\d*$
_

Delete the numeric input, and increment the result.

/(^_|\1__)+$|^(__(___?)?(____)*)\2+$|^(?!(___(____)*)\5+$)/+`

While the result: (^_|\1__)+$ is square, or ^(__(___?)?(____)*)\2+$ contains a nontrivial proper factor that is not of the form 4t+3, or (?!(___(____)*)\5+$) does not contain a nontrivial proper factor that is of the form 4t+3, then...

$
_

... increment the result.

_

Convert to decimal.

All numbers contain a trivial factor not of the form 4t+3, i.e. 1. Since the product of two factors 4t+3 would be of the form 4t+1, the only way a number to only contain nontrivial factors of the form 4t+3 is for the number to be a prime of the form 4t+3. The next step is to consider numbers with nontrivial proper factors which are all of the form 4t+3. This set contains only products of two primes of the form 4t+3 (since 3 primes would generate nontrivial proper factors of the form 4t+1 as the product of two of the primes), so it remains to exclude perfect squares which then leaves Blum integers.

Answer 8

05AB1E,  10  9 bytes

-1 thanks to Adnan (26 is a built-in, ₂, and 1 is the only truthy integer in 05AB1E)

A port of my Jelly answer, just using divisors rather than proper divisors.

∞ʒÑ4%JC27Q

A full program printing an infinite list of the Blum integers.

Try it online!

How?

For an explanation of why this works see my Jelly answer (and add \$(p\cdot q)\mod 4\$ to the list to be converted from binary, noting that this will be \$1\$ for a Blum integer, while \$13\cdot2+1=27\$ and the existence of two final potential false-positives, \$(1,1,0,0,3)\$ and \$(1,1,0,1,1)\$ neither of which can happen since \$p\equiv 1\pmod 4 \implies p^2\equiv 1\pmod 4\$.)

∞ʒÑ4%JC₂-
∞         - the positive integers
 ʒ        - filter keep if truthy under:
  Ñ       -   divisors
   4      -   push four
    %     -   modulo
     J    -   join
      C   -   from binary -> x
       ₂  -   push 26
        - -   subtract -> x-26 (truthy when x=27 as only 1 is truthy in 05AB1E)

Answer 9

Jelly, 14 bytes

ÆfQƑa%ɗ4⁼3,3µ#

Try it online!

Outputs the first \$n\$ Blum integers. Takes \$n\$ on STDIN

-1 byte thanks to Nick Kennedy

How it works

ÆfQƑa%ɗ4⁼3,3µ# - Main link. Takes no arguments
            µ  - Group the previous links into a monad f(k):
Æf             -   Prime factors of k; F
      ɗ4       -   Previous 3 links as a dyad g(F, 4):
  QƑ           -     Are the prime factors unique?
     %         -     Mod each factor by 4
    a          -     And; If the prime factors are unique, yield the
                      factors mod 4, otherwise, yield 0
        ⁼3,3   -   Does that equal [3, 3]?
             # - Read n. Count up k = 0, 1, ... until n such k return true under f(k)

Answer 10

JavaScript (V8),  59  57 bytes

This version is inspired by xnor's answer in Python. We print n if the concatenation of its proper divisors modulo 4 (in ascending order and without repetition) is "133".

for(n=0;g=d=>--d&&g(d)+[[d%4][n%d]];)g(++n)^133||print(n)

Try it online!

---

JavaScript (V8),  76  75 bytes

Prints the sequence 'forever' (i.e. until a recursion error occurs).

for(n=0;g=d=>k%--d?g(d):d;)g(k=p=g(k=++n))*g(k=n/p)^p!=k|~(p&k)&3||print(n)

Try it online!

Commented

for(               // loop:
  n = 0;           //   start with n = 0
  g = d =>         //   define the helper function g
    k % --d ? g(d) //   which returns the highest proper divisor of k
            : d;   //
)                  //
  g(               // get the highest proper divisor of ...
    k = p =        //   ... the highest proper divisor p of ...
      g(k = ++n)   //     ... n, after it's been incremented
  ) *              // and multiply it by
  g(               // the highest proper divisor of
    k = n / p      //   k = n / p
  )                // this product is either 1 (success) or greater than 1
  ^ p != k         // make sure that p is not equal to k
                   // (so the product XOR'ed with p != k must give 0)
  | ~(p & k) & 3   // make sure that both p and k are congruent to 3 mod 4
  || print(n)      // print n if all tests pass

Answer 11

Python 3.8 (pre-release), 134 bytes

f=lambda n,p=[],s=2:sorted(i*j for j in p for i in p if i<j)[:n]if n<len(p)else f(n,p+[s]*(all(s%i for i in range(2,s))and s%4>2),s+1)

Try it online!

Output the first n numbers of the sequence.

Explanation

Creates a list of primes p starting with the empty list. First, check if p has more than n elements (this is frankly quite arbitrary, we clearly need less primes than that.)

If there are, then we output the first n elements of the sorted list of products i*j for each possible duo of i and j in p if i<j to prevent duplicates.

Otherwise check if the counter is s is prime. Recall f with n and either p unchanged if s is composite or p+[s] if s is prime. Also increment s.

Remove the colon before n to get a program which outputs the nth Blum integer, 0-indexed.

Log: 151->150->142->139->138->137->134

Answer 12

Brachylog, 8 bytes

ḋĊ≠%₄ᵛ3&

Try it online!

Acts as an infinite generator.

Explanation

ḋĊ≠%₄ᵛ3&
ḋ         The input's prime decomposition
 Ċ        is a pair
  ≠       of distinct values
   ᵛ      which all
    %₄    modulo 4
      3   equal 3.
       &  The input and the output are the same.

Answer 13

Charcoal, 28 bytes

ＦＮ«≦⊕χＷ⁻³¹↨⁴﹪Φχ∧μ¬﹪χλ⁴≦⊕χ»Ｉχ

Try it online! Link is to verbose version of code. Explanation:

ＦＮ«

Loop the given number of times.

≦⊕χ

Increment the result variable (predefined to 10, which is fortunately less than the first Blum integer).

Ｗ⁻³¹↨⁴﹪Φχ∧μ¬﹪χλ⁴

Take the proper factors of the variable, reduce them modulo 4, interpret the list as a base 4 integer, and repeat while the result is not 31 (133 in base 4)...

≦⊕χ

... increment the result variable.

»Ｉχ

Output the result.

Answer 14

Python 2, 118 112 bytes

Prints the first n Blum integers.

n=input()
P=4
k=3
r=p=[]
while p[n:]<=p:
 if P%k&k/2:r=r+[x*k for x in p];p+=k,
 P*=k*k;k+=1
print sorted(r)[:n]

Try it online!

Uses Wilson's theorem. p keeps track of all primes of the form \$4t+3\$, r is a unique list of all Blum integers that can be created with the primes in p.

Answer 15

jq, 61 bytes

Prints all Blum integers.

0|while(1;.+1)|select([[.%range(2;.)]|indices(0)[]%4]==[1,1])

Try it online!

For all practical reasons 0|while(1;.+1) could be replaced with range(0|-y0), but it feels more like an infinite sequence this way, even if both are limited by the range of representable numbers.