15
\$\begingroup\$

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 so shortest answer wins.

\$\endgroup\$

13 Answers 13

7
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ This is amazing. How does the !=print(n) work? \$\endgroup\$ – wasif Jun 20 at 4:16
  • 1
    \$\begingroup\$ @Wasif print returns None, so we check if the condition on the left (equality) is not None, i.e. we loop while the two factors are congruent to 3 mod 4. \$\endgroup\$ – Recursive Co. Jun 20 at 6:16
  • 1
    \$\begingroup\$ @Wasif It's inequality short-circuiting. \$\endgroup\$ – xnor Jun 20 at 7:36
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ great explanation! \$\endgroup\$ – EliteDaMyth Jun 20 at 13:35
4
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ @DominicvanEssen - good catch! The identical would be necessary when checking only proper divisors (to check both length and values), as I had in one of the first attempts. Now, when checking also the number itself, all with == suffices indeed. \$\endgroup\$ – pajonk Jun 20 at 18:46
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ -1 byte: ÆfQƑa%ɗ4⁼3,3µ# \$\endgroup\$ – Nick Kennedy Jun 19 at 16:11
  • 1
    \$\begingroup\$ @NickKennedy Ah, nice use of a! Thanks! \$\endgroup\$ – caird coinheringaahing Jun 19 at 16:16
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save a byte by replacing 0s`* with ü*θ \$\endgroup\$ – Adnan Jun 20 at 2:00
  • \$\begingroup\$ @Adnan thanks a lot, for some reason I thought this wouldn't work if there are less than 2 prime factors \$\endgroup\$ – ovs Jun 20 at 14:56
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ This is probably just sheer luck, but you can replace 27Q with ₂-, which saves a byte. \$\endgroup\$ – Adnan Jun 20 at 15:29
  • \$\begingroup\$ Nice, thanks! Shocking that 26 has its own byte; how are there enough bytes for everything else?! \$\endgroup\$ – Jonathan Allan Jun 20 at 15:42
  • \$\begingroup\$ Yeah, I believe we had some spare constants left after the rewrite and after some analysis, we came to the conclusion that 26 (no. of letters in the alphabet) seemed to be used commonly. \$\endgroup\$ – Adnan Jun 20 at 17:22
0
\$\begingroup\$

Charcoal, 28 bytes

FN«≦⊕χW⁻³¹↨⁴﹪Φχ∧μ¬﹪χλ⁴≦⊕χ»Iχ

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

FN«

Loop the given number of times.

≦⊕χ

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

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

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.

»Iχ

Output the result.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.