Blum integer

Blum integer is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Definition

A positive integer n is a Blum integer if n = p x q is a semi-prime for which p and q are distinct primes congruent to 3 mod 4. In other words, p and q must be of the form 4t + 3 where t is some non-negative integer.

Example

21 is a Blum integer because it has two prime factors: 3 (= 4 x 0 + 3) and 7 (= 4 x 1 + 3).

Task

Find and show on this page the first 50 Blum integers.

Also show the 26,828th.

Stretch

Find and show the 100,000th, 200,000th, 300,000th and 400,000th Blum integers.

For the first 400,000 Blum integers, show the percentage distribution by final decimal digit (to 3 decimal places). Clearly, such integers can only end in 1, 3, 7 or 9.

Related task

• Semiprime

References

• Wikipedia article Blum integer
• OEIS sequence A016105: Blum integers

C

Translation of: Wren

#include <stdio.h>
#include <locale.h>

void primeFactors(int n, int *factors, int *length) {
    if (n < 2) return;
    int count = 0;
    int inc[8] = {4, 2, 4, 2, 4, 6, 2, 6};
    while (!(n%2)) {
        factors[count++] = 2;
        n /= 2;
    }
    while (!(n%3)) {
        factors[count++] = 3;
        n /= 3;
    }
    while (!(n%5)) {
        factors[count++] = 5;
        n /= 5;
    }
    for (int k = 7, i = 0; k*k <= n; ) {
        if (!(n%k)) {
            factors[count++] = k;
            n /= k;
        } else {
            k += inc[i];
            i = (i + 1) % 8;
        }
    }
    if (n > 1) {
        factors[count++] = n;
    }
    *length = count;
}

int main() {
    int i = 1, j, bc = 0, length = 0;
    int f[20], blum[50], counts[4] = {0}, digits[4] = {1, 3, 5, 7};
    setlocale(LC_NUMERIC, "");
    while (1) {
        primeFactors(i, f, &length);
        if (length == 2 && f[0] != f[1] && f[0] % 4 == 3 && f[1] % 4 == 3) {
            if (bc < 50) blum[bc] = i;
            ++counts[i % 10 / 3];
            ++bc;
            if (bc == 50) {
                printf("First 50 Blum integers:\n");
                for (j = 0; j < 50; ++j) {
                    printf("%3d ", blum[j]);
                    if (!((j+1) % 10)) printf("\n");
                }
                printf("\n");
            } else if (bc == 26828 || !(bc % 100000)) {
                printf("The %'7dth Blum integer is: %'9d\n", bc, i);
                if (bc == 400000) {
                    printf("\n%% distribution of the first 400,000 Blum integers:\n");
                    for (j = 0; j < 4; ++j) {
                        printf("  %6.3f%% end in %d\n", counts[j]/4000.0, digits[j]);
                    }
                    break;
                }
            }
        }
        i += (i % 5 == 3) ? 4 : 2;
    }               
    return 0;
}

Output:

Same as Wren example.

Go

Translation of: Wren

Library: Go-rcu

package main

import (
    "fmt"
    "rcu"
)

func main() {
    blum := make([]int, 50)
    bc := 0
    counts := make([]int, 4)
    i := 1
    for {
        f := rcu.PrimeFactors(i)
        if len(f) == 2 && f[0] != f[1] && f[0]%4 == 3 && f[1]%4 == 3 {
            if bc < 50 {
                blum[bc] = i
            }
            counts[i%10/3]++
            bc++
            if bc == 50 {
                fmt.Println("First 50 Blum integers:")
                rcu.PrintTable(blum, 10, 3, false)
                fmt.Println()
            } else if bc == 26828 || bc%100000 == 0 {
                fmt.Printf("The %7sth Blum integer is: %9s\n", rcu.Commatize(bc), rcu.Commatize(i))
                if bc == 400000 {
                    fmt.Println("\n% distribution of the first 400,000 Blum integers:")
                    for j := 0; j < 4; j++ {
                        fmt.Printf("  %6.3f%% end in %d\n", float64(counts[j])/4000, j)
                    }
                    return
                }
            }
        }
        if i%5 == 3 {
            i += 4
        } else {
            i += 2
        }
    }
}

Output:

Same as Wren example.

Wren

Library: Wren-math

Library: Wren-fmt

import "./math" for Int
import "./fmt" for Fmt

var blum = []
var bc = 0
var counts = { 1: 0, 3: 0, 7: 0, 9: 0 }
var i = 1
while (true) {
    var f = Int.primeFactors(i)
    if (f.count == 2 && f[0] != f[1] && f[0] % 4 == 3 && f[1] % 4 == 3) {
        if (bc < 50) blum.add(i)
        counts[i % 10] = counts[i % 10] + 1
        bc = bc + 1
        if (bc == 50) {
            System.print("First 50 Blum integers:")
            Fmt.tprint("$3d ", blum, 10)
            System.print()
        } else if (bc == 26828 || bc % 1e5 == 0) {
            Fmt.print("The $,9r Blum integer is: $,9d", bc, i)
            if (bc == 400000) {
                System.print("\n\% distribution of the first 400,000 Blum integers:")
                for (j in [1, 3, 7, 9]) {
                    Fmt.print("  $6.3f\% end in $d", counts[j]/4000, j)
                }
                return
            }
        }
    }
    i = (i % 5 == 3) ? i + 4 : i + 2
}

Output:

First 50 Blum integers:
 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 

The  26,828th Blum integer is:   524,273
The 100,000th Blum integer is: 2,075,217
The 200,000th Blum integer is: 4,275,533
The 300,000th Blum integer is: 6,521,629
The 400,000th Blum integer is: 8,802,377

% distribution of the first 400,000 Blum integers:
  25.001% end in 1 
  25.017% end in 3 
  24.997% end in 7 
  24.985% end in 9