Brilliant numbers
You are encouraged to solve this task according to the task description, using any language you may know.
Brilliant numbers are a subset of semiprime numbers. Specifically, they are numbers that are the product of exactly two prime numbers that both have the same number of digits when expressed in base 10.
Brilliant numbers are useful in cryptography and when testing prime factoring algorithms.
- E.G.
- 3 × 3 (9) is a brilliant number.
- 2 × 7 (14) is a brilliant number.
- 113 × 691 (78083) is a brilliant number.
- 2 × 31 (62) is semiprime, but is not a brilliant number (different number of digits in the two factors).
- Task
- Find and display the first 100 brilliant numbers.
- For the orders of magnitude 1 through 6, find and show the first brilliant number greater than or equal to the order of magnitude, and, its position in the series (or the count of brilliant numbers up to that point).
- Stretch
- Continue for larger orders of magnitude.
- See also
Ada
with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions;
with Ada.Text_IO; use Ada.Text_IO;
procedure Brilliant_Numbers is
subtype Prime_Numbers is Positive range 2 .. 10_000_000 with
Dynamic_Predicate => (for all I in 2 .. (Prime_Numbers / 2)
=> (Prime_Numbers mod I) /= 0);
Count, N, FPF, SF, Expo : Integer := 0;
function First_Prime_Factor (N : Integer) return Integer is
I : Integer := 3;
begin
if N mod 2 = 0 then
return 2;
end if;
while I < Integer (Sqrt (Float (N)) + 1.0) loop
if N mod I = 0 then
return I;
end if;
I := I + 2;
end loop;
return N;
end First_Prime_Factor;
begin
while Count < 100 loop
FPF := First_Prime_Factor (N);
SF := N / FPF;
if SF in Prime_Numbers and then FPF'Image'Length = SF'Image'Length then
Put (N'Image);
Count := Count + 1;
if Count mod 6 = 0 then
New_Line;
end if;
end if;
N := N + 1;
end loop;
Count := 0;
N := 0;
loop
FPF := First_Prime_Factor (N);
SF := N / FPF;
if SF in Prime_Numbers and then FPF'Image'Length = SF'Image'Length then
Count := Count + 1;
if N > 10 ** Expo then
Put_Line (N'Image & " is brilliant number:" & Count'Image);
Expo := Expo + 1;
exit when Expo = 7;
end if;
end if;
N := N + 1;
end loop;
end Brilliant_Numbers;
- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 4 is brilliant number: 1 14 is brilliant number: 5 121 is brilliant number: 11 1003 is brilliant number: 74 10201 is brilliant number: 242 100013 is brilliant number: 2505 1018081 is brilliant number: 10538
ALGOL 68
BEGIN # Find Brilliant numbers - semi-primes whose two prime factors have #
# the same number of digits #
PR read "primes.incl.a68" PR # include prime utilities #
INT max prime = 1 010; # maximum prime we will consider #
# should be enough to find the first brilliant number > 10^6 #
[]BOOL prime = PRIMESIEVE max prime; # sieve of primes to max prime #
# construct a table of brilliant numbers #
[ 1 : max prime * max prime ]BOOL brilliant;
FOR n FROM LWB brilliant TO UPB brilliant DO brilliant[ n ] := FALSE OD;
# brilliant numbers where one of the fators is 2 #
brilliant[ 4 ] := TRUE;
FOR p FROM 3 BY 2 TO 7 DO brilliant[ 2 * p ] := TRUE OD;
# brilliant numbers where both factors are odd #
INT p start := 1, p end := 9;
WHILE pstart < max prime DO
FOR p FROM p start BY 2 TO p end DO
IF prime[ p ] THEN
brilliant[ p * p ] := TRUE;
FOR q FROM p + 2 BY 2 TO p end DO
IF prime[ q ] THEN
brilliant[ p * q ] := TRUE
FI
OD
FI
OD;
p start := p end + 2;
p end := ( ( p start - 1 ) * 10 ) - 1;
IF p end > max prime THEN p end := max prime FI
OD;
# show the first 100 brilliant numbers #
INT b count := 0;
FOR n TO UPB brilliant WHILE b count < 100 DO
IF brilliant[ n ] THEN
print( ( whole( n, -6 ) ) );
IF ( b count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
# first brilliant number >= 10^n, n = 1, 2, ..., 6 #
b count := 0;
INT power of 10 := 10;
FOR n TO UPB brilliant DO
IF brilliant[ n ] THEN
b count +:= 1;
IF n >= power of 10 THEN
print( ( "First brilliant number >= ", whole( power of 10, -8 )
, ": " , whole( n, -8 )
, " at position " , whole( b count, -6 )
, newline
)
);
power of 10 *:= 10
FI
FI
OD
END- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10: 10 at position 4 First brilliant number >= 100: 121 at position 11 First brilliant number >= 1000: 1003 at position 74 First brilliant number >= 10000: 10201 at position 242 First brilliant number >= 100000: 100013 at position 2505 First brilliant number >= 1000000: 1018081 at position 10538
AppleScript
use AppleScript version "2.3.1" -- Mac OS X 10.9 (Mavericks) or later.
use sorter : script "Insertion sort" -- <https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript>
on sieveOfEratosthenes(limit)
set mv to missing value
script o
property numberList : makelist(limit, missing value)
end script
set o's numberList's item 2 to 2
set o's numberList's item 3 to 3
repeat with n from 5 to (limit - 2) by 6
set o's numberList's item n to n
tell (n + 2) to set o's numberList's item it to it
end repeat
if (limit - n > 5) then tell (n + 6) to set o's numberList's item it to it
repeat with n from 5 to (limit ^ 0.5 div 1) by 6
if (o's numberList's item n = n) then
repeat with multiple from (n * n) to limit by n
set o's numberList's item multiple to mv
end repeat
end if
tell (n + 2)
if (o's numberList's item it = it) then
repeat with multiple from (it * it) to limit by it
set o's numberList's item multiple to mv
end repeat
end if
end tell
end repeat
return o's numberList's numbers
end sieveOfEratosthenes
on makelist(limit, filler)
if (limit < 1) then return {}
script o
property lst : {filler}
end script
set counter to 1
repeat until (counter + counter > limit)
set o's lst to o's lst & o's lst
set counter to counter + counter
end repeat
if (counter < limit) then set o's lst to o's lst & o's lst's items 1 thru (limit - counter)
return o's lst
end makelist
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on ordinalise(n)
set units to n mod 10
if ((units > 3) or (n div 10 mod 10 is 1) or (units < 1) or (units mod 1 > 0)) then ¬
return (n as text) & "th"
return (n as text) & item units of {"st", "nd", "rd"}
end ordinalise
on task()
script o
-- Enough primes to include the first > the square root of 100,000,000.
property primes : sieveOfEratosthenes(10020)
-- Collector for enough not-quite-ordered brilliants to include the first 100.
property first250 : {}
end script
-- List of data collectors for nine magnitudes.
set {magData, mag, mv} to {{}, 1, missing value}
repeat 9 times
set magData's end to {magnitude:mag, lowest:mv, |count|:0}
set mag to mag * 10
end repeat
-- Calculate the brilliant numbers and store the relevant info.
set {primeMag, counter} to {1, 0}
repeat with k from 1 to (count o's primes)
set thisPrime to o's primes's item k
if (thisPrime ≥ primeMag) then
set primeMag to primeMag * 10
set i to k
end if
repeat with j from i to k
set thisBrill to thisPrime * (o's primes's item j)
if (counter < 250) then
set counter to counter + 1
set o's first250's end to thisBrill
end if
repeat with m from 9 to 1 by -1
set theseData to magData's item m
if (thisBrill ≥ theseData's magnitude) then
if ((theseData's lowest is mv) or (theseData's lowest > thisBrill)) then ¬
set theseData's lowest to thisBrill
set theseData's |count| to (theseData's |count|) + 1
exit repeat
end if
end repeat
end repeat
end repeat
-- Get the first 100 brilliants from the first 250 collected.
tell sorter to sort(o's first250, 1, counter)
set output to {"The first 100 brilliant numbers are:"}
set theseTen to {}
repeat with i from 1 to 100 by 10
repeat with j from i to i + 9
set theseTen's end to (" " & o's first250's item j)'s text -6 thru end
end repeat
set output's end to join(theseTen, "")
set theseTen to {}
end repeat
-- Get the data from the magnitude records.
set counter to 1
repeat with theseData in magData
set output's end to "The first ≥ " & (theseData's magnitude) & ¬
" is the " & ordinalise(counter) & ": " & (theseData's lowest)
set counter to counter + (theseData's |count|)
end repeat
return join(output, linefeed)
end task
task()
- Output:
"The first 100 brilliant numbers are:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
The first ≥ 1 is the 1st: 4
The first ≥ 10 is the 4th: 10
The first ≥ 100 is the 11th: 121
The first ≥ 1000 is the 74th: 1003
The first ≥ 10000 is the 242nd: 10201
The first ≥ 100000 is the 2505th: 100013
The first ≥ 1000000 is the 10538th: 1018081
The first ≥ 10000000 is the 124364th: 10000043
The first ≥ 100000000 is the 573929th: 100140049"
Arturo
brilliant?: function [x][
pf: factors.prime x
and? -> 2 = size pf
-> equal? size digits first pf
size digits last pf
]
brilliants: new []
i: 2
while [100 > size brilliants][
if brilliant? i -> 'brilliants ++ i
i: i + 1
]
print "First 100 brilliant numbers:"
loop split.every: 10 brilliants 'row [
print map to [:string] row 'item -> pad item 4
]
print ""
i: 4
nth: 0
order: 1
while [order =< 6] [
if brilliant? i [
nth: nth + 1
if i >= 10^order [
print ["First brilliant number >= 10 ^" order "is" i "at position" nth]
order: order + 1
]
]
i: i + 1
]
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10 ^ 1 is 10 at position 4 First brilliant number >= 10 ^ 2 is 121 at position 11 First brilliant number >= 10 ^ 3 is 1003 at position 74 First brilliant number >= 10 ^ 4 is 10201 at position 242 First brilliant number >= 10 ^ 5 is 100013 at position 2505 First brilliant number >= 10 ^ 6 is 1018081 at position 10538
C++
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <locale>
#include <vector>
#include <primesieve.hpp>
auto get_primes_by_digits(uint64_t limit) {
primesieve::iterator pi;
std::vector<std::vector<uint64_t>> primes_by_digits;
std::vector<uint64_t> primes;
for (uint64_t p = 10; p <= limit;) {
uint64_t prime = pi.next_prime();
if (prime > p) {
primes_by_digits.push_back(std::move(primes));
p *= 10;
}
primes.push_back(prime);
}
return primes_by_digits;
}
int main() {
std::cout.imbue(std::locale(""));
auto start = std::chrono::high_resolution_clock::now();
auto primes_by_digits = get_primes_by_digits(1000000000);
std::cout << "First 100 brilliant numbers:\n";
std::vector<uint64_t> brilliant_numbers;
for (const auto& primes : primes_by_digits) {
for (auto i = primes.begin(); i != primes.end(); ++i)
for (auto j = i; j != primes.end(); ++j)
brilliant_numbers.push_back(*i * *j);
if (brilliant_numbers.size() >= 100)
break;
}
std::sort(brilliant_numbers.begin(), brilliant_numbers.end());
for (size_t i = 0; i < 100; ++i) {
std::cout << std::setw(5) << brilliant_numbers[i]
<< ((i + 1) % 10 == 0 ? '\n' : ' ');
}
std::cout << '\n';
uint64_t power = 10;
size_t count = 0;
for (size_t p = 1; p < 2 * primes_by_digits.size(); ++p) {
const auto& primes = primes_by_digits[p / 2];
size_t position = count + 1;
uint64_t min_product = 0;
for (auto i = primes.begin(); i != primes.end(); ++i) {
uint64_t p1 = *i;
auto j = std::lower_bound(i, primes.end(), (power + p1 - 1) / p1);
if (j != primes.end()) {
uint64_t p2 = *j;
uint64_t product = p1 * p2;
if (min_product == 0 || product < min_product)
min_product = product;
position += std::distance(i, j);
if (p1 >= p2)
break;
}
}
std::cout << "First brilliant number >= 10^" << p << " is "
<< min_product << " at position " << position << '\n';
power *= 10;
if (p % 2 == 1) {
size_t size = primes.size();
count += size * (size + 1) / 2;
}
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration(end - start);
std::cout << "\nElapsed time: " << duration.count() << " seconds\n";
}
- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1,003 1,007 1,027 1,037 1,067 1,073 1,079
1,081 1,121 1,139 1,147 1,157 1,159 1,189 1,207 1,219 1,241
1,247 1,261 1,271 1,273 1,333 1,343 1,349 1,357 1,363 1,369
First brilliant number >= 10^1 is 10 at position 4
First brilliant number >= 10^2 is 121 at position 11
First brilliant number >= 10^3 is 1,003 at position 74
First brilliant number >= 10^4 is 10,201 at position 242
First brilliant number >= 10^5 is 100,013 at position 2,505
First brilliant number >= 10^6 is 1,018,081 at position 10,538
First brilliant number >= 10^7 is 10,000,043 at position 124,364
First brilliant number >= 10^8 is 100,140,049 at position 573,929
First brilliant number >= 10^9 is 1,000,000,081 at position 7,407,841
First brilliant number >= 10^10 is 10,000,600,009 at position 35,547,995
First brilliant number >= 10^11 is 100,000,000,147 at position 491,316,167
First brilliant number >= 10^12 is 1,000,006,000,009 at position 2,409,600,866
First brilliant number >= 10^13 is 10,000,000,000,073 at position 34,896,253,010
First brilliant number >= 10^14 is 100,000,380,000,361 at position 174,155,363,187
First brilliant number >= 10^15 is 1,000,000,000,000,003 at position 2,601,913,448,897
First brilliant number >= 10^16 is 10,000,001,400,000,049 at position 13,163,230,391,313
First brilliant number >= 10^17 is 100,000,000,000,000,831 at position 201,431,415,980,419
Elapsed time: 1.50048 seconds
Delphi
function Compare(P1,P2: pointer): integer;
{Compare for quick sort}
begin
Result:=Integer(P1)-Integer(P2);
end;
procedure GetBrilliantNumbers(List: TList; Limit: integer);
{Return specified number of Brilliant Numbers in list}
var I,J,P,Stop: integer;
var Sieve: TPrimeSieve;
begin
Sieve:=TPrimeSieve.Create;
try
{build twices as many primes}
Sieve.Intialize(Limit*2);
{Pair every n-digt prime with every n-digit prime}
I:=2;
while true do
begin
J:=I;
{Put primes in J up to next power of 10 - 1}
Stop:=Trunc(Power(10,Trunc(Log10(I))+1));
while J<Stop do
begin
{Get the product}
P:=I * J;
{and store in the list}
List.Add(Pointer(P));
{Exit if we have all the numbers}
if List.Count>=Limit then break;
{Get next prime}
J:=Sieve.NextPrime(J);
end;
{break out of outer loop if done}
if List.Count>=Limit then break;
{Get next prime}
I:=Sieve.NextPrime(I);
end;
{The list won't be in order, so sort them}
List.Sort(Compare);
finally Sieve.Free; end;
end;
procedure ShowBrilliantNumbers(Memo: TMemo);
var List: TList;
var S: string;
var I,D,P: integer;
begin
List:=TList.Create;
try
{Get 10 million brilliant numbers}
GetBrilliantNumbers(List,1000000);
{Show the first 100}
S:='';
for I:=0 to 100-1 do
begin
S:=S+Format('%7d',[Integer(List[I])]);
if (I mod 10)=9 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
{Show additional information}
for D:=1 to 8 do
begin
P:=Trunc(Power(10,D));
{Scan to find for 1st brilliant number >= 10^D }
for I:=0 to List.Count-1 do
if Integer(List[I])>=P then break;
{Display the info}
S:=Format('First brilliant number >= 10^%d is %10d',[D,Integer(List[I])]);
S:=S+Format(' at position %10D', [I]);
Memo.Lines.Add(S);
end;
finally List.Free; end;
end;
- Output:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First brilliant number >= 10^1 is 10 at position 3
First brilliant number >= 10^2 is 121 at position 10
First brilliant number >= 10^3 is 1003 at position 73
First brilliant number >= 10^4 is 10201 at position 241
First brilliant number >= 10^5 is 100013 at position 2504
First brilliant number >= 10^6 is 1018081 at position 10537
First brilliant number >= 10^7 is 10000043 at position 124363
First brilliant number >= 10^8 is 100140049 at position 573928
Elapsed Time: 185.451 ms.
EasyLang
fastfunc factor num .
if num mod 2 = 0
if num = 2
return 1
.
return 2
.
i = 3
while i <= sqrt num
if num mod i = 0
return i
.
i += 2
.
return 1
.
func brilliant n .
f1 = factor n
if f1 = 1
return 0
.
f2 = n div f1
if floor log10 f1 <> floor log10 f2
return 0
.
if factor f1 = 1 and factor f2 = 1
return 1
.
return 0
.
proc main . .
i = 2
while cnt < 100
if brilliant i = 1
cnt += 1
write i & " "
.
i += 1
.
print "\n"
i = 2
cnt = 0
mag = 1
repeat
if brilliant i = 1
cnt += 1
if i >= mag
print i & " (" & cnt & ")"
mag *= 10
.
.
until mag = 10000000
i += 1
.
.
main
- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 4 (1) 10 (4) 121 (11) 1003 (74) 10201 (242) 100013 (2505) 1018081 (10538)
Factor
USING: assocs formatting grouping io kernel lists lists.lazy
math math.functions math.primes.factors prettyprint
project-euler.common sequences ;
MEMO: brilliant? ( n -- ? )
factors [ length 2 = ] keep
[ number-length ] map all-eq? and ;
: lbrilliant ( -- list )
2 lfrom [ brilliant? ] lfilter 1 lfrom lzip ;
: first> ( m -- n )
lbrilliant swap '[ first _ >= ] lfilter car ;
: .first> ( n -- )
dup first> first2
"First brilliant number >= %7d: %7d at position %5d\n"
printf ;
100 lbrilliant ltake list>array keys 10 group simple-table. nl
{ 1 2 3 4 5 6 } [ 10^ .first> ] each
- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10: 10 at position 4 First brilliant number >= 100: 121 at position 11 First brilliant number >= 1000: 1003 at position 74 First brilliant number >= 10000: 10201 at position 242 First brilliant number >= 100000: 100013 at position 2505 First brilliant number >= 1000000: 1018081 at position 10538
FreeBASIC
function is_prime( n as uinteger ) as boolean
if n = 2 then return true
if n<2 or n mod 2 = 0 then return false
for i as uinteger = 3 to sqr(n) step 2
if (n mod i) = 0 then return false
next i
return true
end function
function first_prime_factor( n as uinteger ) as uinteger
if n mod 2 = 0 then return 2
for i as uinteger = 3 to sqr(n) step 2
if (n mod i) = 0 then return i
next i
return n
end function
dim as uinteger count = 0, n = 0, ff, sf, expo = 0
while count<100
ff = first_prime_factor(n)
sf = n/ff
if is_prime(sf) and len(str(ff)) = len(str(sf)) then
print n,
count = count + 1
if count mod 6 = 0 then print
end if
n = n + 1
wend
print
count = 0
n = 0
do
ff = first_prime_factor(n)
sf = n/ff
if is_prime(sf) and len(str(ff)) = len(str(sf)) then
count = count + 1
if n > 10^expo then
print n;" is brilliant #"; count
expo = expo + 1
if expo = 9 then end
end if
end if
n = n + 1
loop
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 4 is brilliant #1 14 is brilliant #5 121 is brilliant #11 1003 is brilliant #74 10201 is brilliant #242 100013 is brilliant #2505 1018081 is brilliant #10538 10000043 is brilliant #124364
FutureBasic
Thanks Ken and Bernie
#build Optimization 3
#build Architecture "Apple Silicon"
// #build Architecture "Intel"
// #build Architecture "Universal"
local fn isPrime( v as Uint64 ) as bool
if v < 2 then exit fn = NO
select 0
if ( ( v - 2 ) == 0 || ( v - 3 ) == 0 ) then exit fn = YES
if ( ( v % 2 ) == 0 || ( v % 3 ) == 0 ) then exit fn = NO
end select
Uint64 f = 5
while f*f <= v
if v mod f == 0 then exit fn = no
f += 2
if v mod f == 0 then exit fn = no
f += 4
wend
end fn = yes
local fn FirstPrimeFactor( n as UInt64 ) as UInt64
UInt64 i
if n mod 2 == 0 then exit fn = 2
if n mod 3 == 0 then exit fn = 3
i = 5
while i*i <= n
if n mod i == 0 then exit fn = i
i += 2
if n mod i == 0 then exit fn = i
i += 4
wend
end fn = n
local fn DoBrilliants( expoLimit as UInt64 ) as CFMutableStringRef
UInt64 count = 0, n = 0, ff, sf, expo = 0
CFMutableStringRef mutStr = fn MutableStringWithString( @"\nFirst 100 brilliant numbers:\n" )
do
ff = fn FirstPrimeFactor( n )
sf = n/ff
if fn IsPrime( sf ) && len( str(ff) ) == len( str(sf) )
MutableStringAppendFormat( mutStr, @"%7u\b", n )
count++
if count mod 10 == 0 then MutableStringAppendFormat( mutStr, @"\n" )
end if
n++
until count == 100
MutableStringAppendFormat( mutStr, @"\n" ) : count = 0 : n = 0
while ( expo != expoLimit )
ff = fn FirstPrimeFactor( n )
sf = n/ff
if fn IsPrime( sf ) && len( str(ff) ) = len( str(sf) )
count++
if ( n >= 10^expo )
MutableStringAppendFormat( mutStr, @"%10u (%6d * %-6d) => 10^%d is brilliant at Position No. %d\n", n, ff, sf, expo, count )
expo++
end if
end if
n++
wend
end fn = mutStr
CFTimeInterval t : t = fn CACurrentMediaTime
CFStringRef brilliants : brilliants = fn DoBrilliants( 7 )
printf @"%@\n\t\tTime = %.f milliseconds", brilliants, (fn CACurrentMediaTime - t) * 1000
HandleEvents- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
4 ( 2 * 2 ) => 10^0 is brilliant at Position No. 1
10 ( 2 * 5 ) => 10^1 is brilliant at Position No. 4
121 ( 11 * 11 ) => 10^2 is brilliant at Position No. 11
1003 ( 17 * 59 ) => 10^3 is brilliant at Position No. 74
10201 ( 101 * 101 ) => 10^4 is brilliant at Position No. 242
100013 ( 103 * 971 ) => 10^5 is brilliant at Position No. 2505
1018081 ( 1009 * 1009 ) => 10^6 is brilliant at Position No. 10538
Time = 450 milliseconds
Using bit-twiddling and the Sieve of Eratosthenes, this code by Jay is exponentially faster than the above.
_top = 100000000 // 100m is largest magnitude this code can handle
_max = 11000 // Number of primes in list
_prime = 0
_notPrime = 1
uint16 primes(_max)
uint8 bits(_top / 7)
ptr gBase : gBase = @bits( 0 )
void local fn init
print @"\n A brilliant number is the product of two primes of the same magnitude."
print @"\n First 100 brilliant numbers:"
ptr p = @primes(0)
uint64 n1 = 2, n2 = 2
while n1 < _max // Create list of primes via sieve of Eratosthenes
if primes(n1) == _prime
% p, n1 // add n1 to list of primes
p += 2
n2 = n1 << 1
while n2 < _max
primes(n2) = _notPrime // mark all multiples of n1 as not prime
n2 += n1
wend
end if
n1 ++
wend
end fn
void local fn brilliants
ptr pn1 = @primes(0), pn2 = pn1
uint64 mag = 10, n, limit = _top / 3
do
while {pn2} < mag
n = {pn1} * {pn2} // mark product of 2 primes as brilliant
if n >= limit then exit fn
bits( n >> 3 ) = bits( n >> 3 ) or bit( n and 7 )
pn2 += 2
wend
pn1 += 2 : pn2 = pn1
if {pn1} > mag then mag *= 10 : if mag == _top then mag = limit
until 0
stop
end fn
void local fn show
uint64 count = 0, mag = 1, b, n, v
ptr p = gBase
while count < 100
v = peek int( p )
b = 0
while v
if v and (1 << b)
v -= (1 << b)
n = ((p - gBase) << 3) + b
count++
print fn StringWithFormat(@"%7d", n);
if count mod 10 == 0 then print
if n >= mag
mda_add 2 = count : mda_add = n
mag *= 10
end if
end if
b++
wend
p += 4
wend
//============================
while mag < _top //search for next magnitude
while p < @bits(mag >> 3) // count up to byte before magnitude
v = [p]
while v
count++
v = v and (v-1) // clear lowest 1 bit in v
wend
p += 8 // move to next 64 bits
wend
// least-of-magnitude will be next number found
while peek int( p ) == 0 : p += 4 : wend
//v = peek int( p )
b = 0
while peek int( p )
if peek int( p ) and (1 << b)
count++
poke int p, peek int( p ) - (1 << b) // Bit has been counted so remove it
// get value of brilliant number
mda_add = @(((p - gBase) << 3) + b) //add it to array
mda_add 2 = count
mag *= 10
end if
b++
wend
p += 4
wend
//============================
print @"\n First brilliant number of each magnitude:"
count = 0
while mda(count)
printf @"%26d is brilliant number #%d", mda_integer(count), mda_integer 2(count)
count++
wend
end fn
window 1, @"Brilliant Numbers"
CFTimeInterval t : t = fn CACurrentMediaTime
fn init
fn brilliants
fn show
printf @"\n Time = %.2f milliseconds.", 1000 * (fn CACurrentMediaTime - t)
handleevents- Output:
A brilliant number is the product of two primes of the same magnitude.
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First brilliant number of each magnitude:
4 is brilliant number #1
10 is brilliant number #4
121 is brilliant number #11
1003 is brilliant number #74
10201 is brilliant number #242
100013 is brilliant number #2505
1018081 is brilliant number #10538
10000043 is brilliant number #124364
Time = 5.88 milliseconds.
Go
package main
import (
"fmt"
"math"
"rcu"
"sort"
)
var primes = rcu.Primes(1e8 - 1)
type res struct {
bc interface{}
next int
}
func getBrilliant(digits, limit int, countOnly bool) res {
var brilliant []int
count := 0
pow := 1
next := math.MaxInt
for k := 1; k <= digits; k++ {
var s []int
for _, p := range primes {
if p >= pow*10 {
break
}
if p > pow {
s = append(s, p)
}
}
for i := 0; i < len(s); i++ {
for j := i; j < len(s); j++ {
prod := s[i] * s[j]
if prod < limit {
if countOnly {
count++
} else {
brilliant = append(brilliant, prod)
}
} else {
if next > prod {
next = prod
}
break
}
}
}
pow *= 10
}
if countOnly {
return res{count, next}
}
return res{brilliant, next}
}
func main() {
fmt.Println("First 100 brilliant numbers:")
brilliant := getBrilliant(2, 10000, false).bc.([]int)
sort.Ints(brilliant)
brilliant = brilliant[0:100]
for i := 0; i < len(brilliant); i++ {
fmt.Printf("%4d ", brilliant[i])
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Println()
for k := 1; k <= 13; k++ {
limit := int(math.Pow(10, float64(k)))
r := getBrilliant(k, limit, true)
total := r.bc.(int)
next := r.next
climit := rcu.Commatize(limit)
ctotal := rcu.Commatize(total + 1)
cnext := rcu.Commatize(next)
fmt.Printf("First >= %18s is %14s in the series: %18s\n", climit, ctotal, cnext)
}
}
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First >= 10 is 4 in the series: 10 First >= 100 is 11 in the series: 121 First >= 1,000 is 74 in the series: 1,003 First >= 10,000 is 242 in the series: 10,201 First >= 100,000 is 2,505 in the series: 100,013 First >= 1,000,000 is 10,538 in the series: 1,018,081 First >= 10,000,000 is 124,364 in the series: 10,000,043 First >= 100,000,000 is 573,929 in the series: 100,140,049 First >= 1,000,000,000 is 7,407,841 in the series: 1,000,000,081 First >= 10,000,000,000 is 35,547,995 in the series: 10,000,600,009 First >= 100,000,000,000 is 491,316,167 in the series: 100,000,000,147 First >= 1,000,000,000,000 is 2,409,600,866 in the series: 1,000,006,000,009 First >= 10,000,000,000,000 is 34,896,253,010 in the series: 10,000,000,000,073
Haskell
import Control.Monad (join)
import Data.Bifunctor (bimap)
import Data.List (intercalate, transpose)
import Data.List.Split (chunksOf, splitWhen)
import Data.Numbers.Primes (primeFactors)
import Text.Printf (printf)
-------------------- BRILLIANT NUMBERS -------------------
isBrilliant :: (Integral a, Show a) => a -> Bool
isBrilliant n = case primeFactors n of
[a, b] -> length (show a) == length (show b)
_ -> False
--------------------------- TEST -------------------------
main :: IO ()
main = do
let indexedBrilliants =
zip
[1 ..]
(filter isBrilliant [1 ..])
putStrLn $
table " " $
chunksOf 10 $
show . snd
<$> take 100 indexedBrilliants
putStrLn "(index, brilliant)"
mapM_ print $
take 6 $
fmap (fst . head) $
splitWhen
(uncurry (<) . join bimap (length . show . snd))
$ zip indexedBrilliants (tail indexedBrilliants)
------------------------- DISPLAY ------------------------
table :: String -> [[String]] -> String
table gap rows =
let ws = maximum . fmap length <$> transpose rows
pw = printf . flip intercalate ["%", "s"] . show
in unlines $ intercalate gap . zipWith pw ws <$> rows
- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 (index, brilliant) (1,4) (4,10) (11,121) (74,1003) (242,10201) (2505,100013)
J
oprimes=: {{ NB. all primes of order y
p:(+i.)/-/\ p:inv +/\1 9*10^y
}}
obrill=: {{ NB. all brilliant numbers of order y primes
~.,*/~oprimes y
}}
brillseq=: {{ NB. sequences of brilliant numbers up through order y-1 primes
/:~;obrill each i.y
}}
Task examples:
10 10 $brillseq 2
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
NB. order, index, value
(brillseq 4) (],.(I. 10^]) ([,.{) [) 1 2 3 4 5 6
1 3 10
2 10 121
3 73 1003
4 241 10201
5 2504 100013
6 10537 1018081
Stretch goal (results are order, index, value):
(brillseq 4) (],.(I. 10^]) ([,.{) [) ,7
7 124363 10000043
(brillseq 5) (],.(I. 10^]) ([,.{) [) 8 9
8 573928 100140049
9 7407840 1000000081
Java
Uses the PrimeGenerator class from Extensible prime generator#Java.
import java.util.*;
public class BrilliantNumbers {
public static void main(String[] args) {
var primesByDigits = getPrimesByDigits(100000000);
System.out.println("First 100 brilliant numbers:");
List<Integer> brilliantNumbers = new ArrayList<>();
for (var primes : primesByDigits) {
int n = primes.size();
for (int i = 0; i < n; ++i) {
int prime1 = primes.get(i);
for (int j = i; j < n; ++j) {
int prime2 = primes.get(j);
brilliantNumbers.add(prime1 * prime2);
}
}
if (brilliantNumbers.size() >= 100)
break;
}
Collections.sort(brilliantNumbers);
for (int i = 0; i < 100; ++i) {
char c = (i + 1) % 10 == 0 ? '\n' : ' ';
System.out.printf("%,5d%c", brilliantNumbers.get(i), c);
}
System.out.println();
long power = 10;
long count = 0;
for (int p = 1; p < 2 * primesByDigits.size(); ++p) {
var primes = primesByDigits.get(p / 2);
long position = count + 1;
long minProduct = 0;
int n = primes.size();
for (int i = 0; i < n; ++i) {
long prime1 = primes.get(i);
var primes2 = primes.subList(i, n);
int q = (int)((power + prime1 - 1) / prime1);
int j = Collections.binarySearch(primes2, q);
if (j == n)
continue;
if (j < 0)
j = -(j + 1);
long prime2 = primes2.get(j);
long product = prime1 * prime2;
if (minProduct == 0 || product < minProduct)
minProduct = product;
position += j;
if (prime1 >= prime2)
break;
}
System.out.printf("First brilliant number >= 10^%d is %,d at position %,d\n",
p, minProduct, position);
power *= 10;
if (p % 2 == 1) {
long size = primes.size();
count += size * (size + 1) / 2;
}
}
}
private static List<List<Integer>> getPrimesByDigits(int limit) {
PrimeGenerator primeGen = new PrimeGenerator(100000, 100000);
List<List<Integer>> primesByDigits = new ArrayList<>();
List<Integer> primes = new ArrayList<>();
for (int p = 10; p <= limit; ) {
int prime = primeGen.nextPrime();
if (prime > p) {
primesByDigits.add(primes);
primes = new ArrayList<>();
p *= 10;
}
primes.add(prime);
}
return primesByDigits;
}
}
- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1,003 1,007 1,027 1,037 1,067 1,073 1,079
1,081 1,121 1,139 1,147 1,157 1,159 1,189 1,207 1,219 1,241
1,247 1,261 1,271 1,273 1,333 1,343 1,349 1,357 1,363 1,369
First brilliant number >= 10^1 is 10 at position 4
First brilliant number >= 10^2 is 121 at position 11
First brilliant number >= 10^3 is 1,003 at position 74
First brilliant number >= 10^4 is 10,201 at position 242
First brilliant number >= 10^5 is 100,013 at position 2,505
First brilliant number >= 10^6 is 1,018,081 at position 10,538
First brilliant number >= 10^7 is 10,000,043 at position 124,364
First brilliant number >= 10^8 is 100,140,049 at position 573,929
First brilliant number >= 10^9 is 1,000,000,081 at position 7,407,841
First brilliant number >= 10^10 is 10,000,600,009 at position 35,547,995
First brilliant number >= 10^11 is 100,000,000,147 at position 491,316,167
First brilliant number >= 10^12 is 1,000,006,000,009 at position 2,409,600,866
First brilliant number >= 10^13 is 10,000,000,000,073 at position 34,896,253,010
First brilliant number >= 10^14 is 100,000,380,000,361 at position 174,155,363,187
First brilliant number >= 10^15 is 1,000,000,000,000,003 at position 2,601,913,448,897
jq
Also works with gojq and fq
The following implementation has been selected for its combination of conceptual simplicity and speed. It turns out that using `is_prime` is significantly faster than adapting the jq code for `is_semiprime` at Semiprime#jq.
def is_brilliant:
. as $in
| sqrt as $sqrt
| def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else 23
| until( . > $sqrt or ($n % . == 0); .+2)
| . * . > $n
end;
{i: 2, n: .}
| until( (.i > $sqrt) or .result;
if .n % .i == 0
then .n /= .i
| if (.i|tostring|length) == (.n|tostring|length)
# notice there is no need to check that .i is prime
and (.n | is_prime)
then .result = 1
else .result = 0
end
else .i += 1
end)
| .result == 1;
# Output a stream of brilliant numbers
def brilliants:
4,6,9,10,14, (range(15;infinite;2) | select(is_brilliant));
def monitor(generator; $power):
pow(10; $power) as $power
| label $out
| foreach generator as $x ({n: 0, p: -1, watch: 1};
.n += 1
| if $x >= .watch
then .emit = true
| .watch *= 10 | .p += 1
| if .watch >= $power then ., break $out else . end
else .emit = null
end;
select(.emit) | [.p, .n, $x]) ;
"The first 100 brilliant numbers:",
[limit(100; brilliants)],
"\n[power of 10, index, brilliant]",
monitor(brilliants; 7)- Output:
The first 100 brilliant numbers: [4,6,9,10,14,15,21,25,35,49,121,143,169,187,209,221,247,253,289,299,319,323,341,361,377,391,403,407,437,451,473,481,493,517,527,529,533,551,559,583,589,611,629,649,667,671,689,697,703,713,731,737,767,779,781,793,799,803,817,841,851,869,871,893,899,901,913,923,943,949,961,979,989,1003,1007,1027,1037,1067,1073,1079,1081,1121,1139,1147,1157,1159,1189,1207,1219,1241,1247,1261,1271,1273,1333,1343,1349,1357,1363,1369] [power of 10, index, brilliant] [0,1,4] [1,4,10] [2,11,121] [3,74,1003] [4,242,10201] [5,2505,100013] [6,10538,1018081]
Julia
using Primes
function isbrilliant(n)
p = factor(n).pe
return (length(p) == 1 && p[1][2] == 2) ||
length(p) == 2 && ndigits(p[1][1]) == ndigits(p[2][1]) && p[1][2] == p[2][2] == 1
end
function testbrilliants()
println("First 100 brilliant numbers:")
foreach(p -> print(lpad(p[2], 5), p[1] % 20 == 0 ? "\n" : ""),
enumerate(filter(isbrilliant, 1:1370)))
bcount, results, positions = 0, zeros(Int, 9), zeros(Int, 9)
for n in 1:10^10
if isbrilliant(n)
bcount += 1
for i in 1:9
if n >= 10^i && results[i] == 0
results[i] = n
positions[i] = bcount
println("First >=", lpad(10^i, 12), " is", lpad(bcount, 8),
" in the series: $n")
end
end
end
end
return results, positions
end
testbrilliants()
- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First >= 10 is 4 in the series: 10
First >= 100 is 11 in the series: 121
First >= 1000 is 74 in the series: 1003
First >= 10000 is 242 in the series: 10201
First >= 100000 is 2505 in the series: 100013
First >= 1000000 is 10538 in the series: 1018081
First >= 10000000 is 124364 in the series: 10000043
First >= 100000000 is 573929 in the series: 100140049
First >= 1000000000 is 7407841 in the series: 1000000081
Mathematica /Wolfram Language
ClearAll[PrimesDecade]
PrimesDecade[n_Integer] := Module[{bounds},
bounds = {PrimePi[10^n] + 1, PrimePi[10^(n + 1) - 1]};
Prime[Range @@ bounds]
]
ds = Union @@ Table[Union[Times @@@ Tuples[PrimesDecade[d], 2]], {d, 0, 4}];
Multicolumn[Take[ds, 100], {Automatic, 8}, Appearance -> "Horizontal"]
sel = Min /@ GatherBy[Select[ds, GreaterEqualThan[10]], IntegerLength];
Grid[{#, FirstPosition[ds, #][[1]]} & /@ sel]
- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 10 4 121 11 1003 74 10201 242 100013 2505 1018081 10538 10000043 124364 100140049 573929 1000000081 7407841
Nim
import std/[algorithm, math, strformat, strutils]
func primes(lim: Natural): seq[Natural] =
## Build list of primes using a sieve of Erathostenes.
var composite = newSeq[bool]((lim + 1) shr 1)
composite[0] = true
for n in countup(3, int(sqrt(lim.toFloat)), 2):
if not composite[n shr 1]:
for k in countup(n * n, lim, 2 * n):
composite[k shr 1] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n shr 1]:
result.add n
func getPrimesByDigits(lim: Natural): seq[seq[Natural]] =
## Distribute primes according to their number of digits.
var p = 10
result.add @[]
for prime in primes(lim):
if prime > p:
p *= 10
if p > 10 * lim: break
result.add @[]
result[^1].add prime
let primesByDigits = getPrimesByDigits(10^9-1)
###
echo "First 100 brilliant numbers:"
var brilliantNumbers: seq[Natural]
for primes in primesByDigits:
for i in 0..primes.high:
for j in 0..i:
brilliantNumbers.add primes[i] * primes[j]
if brilliantNumbers.len >= 100: break
brilliantNumbers.sort()
for i in 0..99:
stdout.write &"{brilliantNumbers[i]:>5}"
if i mod 10 == 9: echo()
echo()
###
var power = 10
var count = 0
for p in 1..<(2 * primesByDigits.len):
let primes = primesByDigits[p shr 1]
var pos = count + 1
var minProduct = int.high
for i, p1 in primes:
let j = primes.toOpenArray(i, primes.high).lowerBound((power + p1 - 1) div p1)
let p2 = primes[i + j]
let product = p1 * p2
if product < minProduct:
minProduct = product
inc pos, j
if p1 >= p2: break
echo &"First brilliant number ⩾ 10^{p:<2} is {minProduct} at position {insertSep($pos)}"
power *= 10
if p mod 2 == 1:
inc count, primes.len * (primes.len + 1) div 2
- Output:
Most of the execution time is used to fill the sieve of Erathostenes.
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First brilliant number ⩾ 10^1 is 10 at position 4
First brilliant number ⩾ 10^2 is 121 at position 11
First brilliant number ⩾ 10^3 is 1003 at position 74
First brilliant number ⩾ 10^4 is 10201 at position 242
First brilliant number ⩾ 10^5 is 100013 at position 2_505
First brilliant number ⩾ 10^6 is 1018081 at position 10_538
First brilliant number ⩾ 10^7 is 10000043 at position 124_364
First brilliant number ⩾ 10^8 is 100140049 at position 573_929
First brilliant number ⩾ 10^9 is 1000000081 at position 7_407_841
First brilliant number ⩾ 10^10 is 10000600009 at position 35_547_995
First brilliant number ⩾ 10^11 is 100000000147 at position 491_316_167
First brilliant number ⩾ 10^12 is 1000006000009 at position 2_409_600_866
First brilliant number ⩾ 10^13 is 10000000000073 at position 34_896_253_010
First brilliant number ⩾ 10^14 is 100000380000361 at position 174_155_363_187
First brilliant number ⩾ 10^15 is 1000000000000003 at position 2_601_913_448_897
First brilliant number ⩾ 10^16 is 10000001400000049 at position 13_163_230_391_313
First brilliant number ⩾ 10^17 is 100000000000000831 at position 201_431_415_980_419
Perl
use strict;
use warnings;
use feature 'say';
use List::AllUtils <max head firstidx uniqint>;
use ntheory <primes is_semiprime forsetproduct>;
sub table { my $t = shift() * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
my(@B,@Br);
for my $oom (1..5) {
my @P = grep { $oom == length } @{primes(10**$oom)};
forsetproduct { is_semiprime($_[0] * $_[1]) and push @B, $_[0] * $_[1] } \@P, \@P;
@Br = uniqint sort { $a <=> $b } @Br, @B;
}
say "First 100 brilliant numbers:\n" . table 10, head 100, @Br;
for my $oom (1..9) {
my $key = firstidx { $_ > 10**$oom } @Br;
printf "First >= %13s is position %9s in the series: %13s\n", comma(10**$oom), comma($key), comma $Br[$key];
}
- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First >= 10 is position 4 in the series: 14
First >= 100 is position 10 in the series: 121
First >= 1,000 is position 73 in the series: 1,003
First >= 10,000 is position 241 in the series: 10,201
First >= 100,000 is position 2,504 in the series: 100,013
First >= 1,000,000 is position 10,537 in the series: 1,018,081
First >= 10,000,000 is position 124364 in the series: 10,000,043
First >= 100,000,000 is position 573929 in the series: 100,140,049
First >= 1,000,000,000 is position 7407841 in the series: 1,000,000,081
Faster approach
use 5.020;
use strict;
use warnings;
use ntheory qw(:all);
use experimental qw(signatures);
sub is_briliant_number ($n) {
is_semiprime($n) || return;
my @f = factor($n);
length($f[0]) == length($f[1]);
}
sub next_brilliant_number ($n) {
++$n while not is_briliant_number($n);
$n;
}
sub brilliant_numbers_count ($n) {
use integer;
my $count = 0;
my $len = length(sqrtint($n));
foreach my $k (1 .. $len - 1) {
my $pi = prime_count(10**($k - 1), 10**$k - 1);
$count += binomial($pi, 2) + $pi;
}
my $min = 10**($len - 1);
my $max = 10**$len - 1;
my $pi_min = prime_count($min);
my $pi_max = prime_count($max);
my $j = -1;
forprimes {
if ($_*$_ <= $n) {
$count += (($max <= $n/$_) ? $pi_max : prime_count($n/$_)) - $pi_min - ++$j;
}
else {
lastfor;
}
} $min, $max;
return $count;
}
say "First 100 brilliant numbers:";
my @nums;
for (my $k = 1 ; scalar(@nums) < 100 ; ++$k) {
push(@nums, $k) if is_briliant_number($k);
}
while (@nums) {
my @slice = splice(@nums, 0, 10);
say join ' ', map { sprintf("%4s", $_) } @slice;
}
say '';
foreach my $n (1 .. 13) {
my $v = next_brilliant_number(vecprod((10) x $n));
printf("First brilliant number >= 10^%d is %s", $n, $v);
printf(" at position %s\n", brilliant_numbers_count($v));
}
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10^1 is 10 at position 4 First brilliant number >= 10^2 is 121 at position 11 First brilliant number >= 10^3 is 1003 at position 74 First brilliant number >= 10^4 is 10201 at position 242 First brilliant number >= 10^5 is 100013 at position 2505 First brilliant number >= 10^6 is 1018081 at position 10538 First brilliant number >= 10^7 is 10000043 at position 124364 First brilliant number >= 10^8 is 100140049 at position 573929 First brilliant number >= 10^9 is 1000000081 at position 7407841 First brilliant number >= 10^10 is 10000600009 at position 35547995 First brilliant number >= 10^11 is 100000000147 at position 491316167 First brilliant number >= 10^12 is 1000006000009 at position 2409600866 First brilliant number >= 10^13 is 10000000000073 at position 34896253010
Phix
Replaced with C++ translation; much faster and now goes comfortably to 1e15 even on 32 bit. You can run this online here.
-- -- demo\rosetta\BrilliantNumbers.exw -- ================================= -- with javascript_semantics requires("1.0.2") -- (for in) atom t0 = time() function get_primes_by_digits(integer limit) sequence primes = get_primes_le(power(10,limit)), primes_by_digits = {} integer p = 10 while length(primes) do integer pi = abs(binary_search(p,primes))-1 primes_by_digits &= {primes[1..pi]} primes = primes[pi+1..$] p*= 10 end while return primes_by_digits end function sequence primes_by_digits = get_primes_by_digits(8) procedure first100() sequence brilliant_numbers = {} for primes in primes_by_digits do for i=1 to length(primes) do --see talk page -- for j=i to length(primes) do for j=1 to i do brilliant_numbers &= primes[i]*primes[j] end for end for if length(brilliant_numbers)>=100 then exit end if end for brilliant_numbers = sort(brilliant_numbers)[1..100] sequence j100 = join_by(brilliant_numbers,1,10," ","\n","%,5d") printf(1,"First 100 brilliant numbers:\n%s\n\n",{j100}) end procedure first100() atom pwr = 10, count = 0 for p=1 to 2*length(primes_by_digits)-1 do sequence primes = primes_by_digits[floor(p/2)+1] atom pos = count+1, min_product = 0 for i=1 to length(primes) do integer p1 = primes[i], j = abs(binary_search(floor((pwr+p1-1)/p1),primes,i)) if j<=length(primes) then -- (always is, I think) integer p2 = primes[j] atom prod = p1*p2 if min_product=0 or prod<min_product then min_product = prod end if pos += j-i if p1>=p2 then exit end if end if end for printf(1,"First brilliant number >= 10^%d is %,d at position %,d\n", {p, min_product, pos}) pwr *= 10; if odd(p) then integer size = length(primes) count += size * (size + 1) / 2; end if end for ?elapsed(time()-t0) {} = wait_key()
- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1,003 1,007 1,027 1,037 1,067 1,073 1,079
1,081 1,121 1,139 1,147 1,157 1,159 1,189 1,207 1,219 1,241
1,247 1,261 1,271 1,273 1,333 1,343 1,349 1,357 1,363 1,369
First brilliant number >= 10^1 is 10 at position 4
First brilliant number >= 10^2 is 121 at position 11
First brilliant number >= 10^3 is 1,003 at position 74
First brilliant number >= 10^4 is 10,201 at position 242
First brilliant number >= 10^5 is 100,013 at position 2,505
First brilliant number >= 10^6 is 1,018,081 at position 10,538
First brilliant number >= 10^7 is 10,000,043 at position 124,364
First brilliant number >= 10^8 is 100,140,049 at position 573,929
First brilliant number >= 10^9 is 1,000,000,081 at position 7,407,841
First brilliant number >= 10^10 is 10,000,600,009 at position 35,547,995
First brilliant number >= 10^11 is 100,000,000,147 at position 491,316,167
First brilliant number >= 10^12 is 1,000,006,000,009 at position 2,409,600,866
First brilliant number >= 10^13 is 10,000,000,000,073 at position 34,896,253,010
First brilliant number >= 10^14 is 100,000,380,000,361 at position 174,155,363,187
First brilliant number >= 10^15 is 1,000,000,000,000,003 at position 2,601,913,448,897
"3.3s"
Prolog
works with swi-prolog
factors(N, Flist):-
factors(N, 2, 0, Flist).
factors(1, _, _, []).
factors(_, _, Cnt, []):- Cnt > 1,!.
factors(N, Start, Cnt, [Fac|FList]):-
N1 is floor(sqrt(N)),
between(Start, N1, Fac),
N mod Fac =:= 0,!,
N2 is N div Fac,
Cnt1 is Cnt + 1,
factors(N2, Fac, Cnt1, FList).
factors(N, _, _, [N]):- N >= 2.
brilliantList(Start, Limit, List):-
findall(N, brilliants(Start, Limit, N), List).
nextBrilliant(Start, N):-
brilliants(Start, inf, N).
isBrilliant(N):-
brilliants(2, inf, N).
brilliants(Start, Limit, N):-
between(Start, Limit, N),
factors(N,[F1,F2]),
F1 * F2 =:= N,
digits(F1, D1), digits(F2, D2),
D1 =:= D2.
digits(N, D):-
D is 1 + floor(log10(N)).
%% generate results
run(LimitList):-
run(LimitList, 0, 2).
run([], _, _).
run([Limit|LList], OldCount, OldLimit):-
Limit1 is Limit - 1,
statistics(runtime,[Start|_]),
brilliantList(OldLimit, Limit1, BList),
length(BList, Cnt),
Cnt1 is OldCount + Cnt,
Index is Cnt1 + 1,
nextBrilliant(Limit, Bril),!,
statistics(runtime,[Stop|_]),
Time is Stop - Start,
writef('first >=%8r is%8r at position%6r [time:%6r]', [Limit, Bril, Index, Time]),nl,
run(LList, Cnt1, Limit).
showList(List, Limit):-
findnsols(Limit, X, (member(X, List), writef('%5r', [X])), _),
nl, fail.
showList(_, _).
do:-findnsols(100, B, isBrilliant(B), BList),!,
showList(BList, 10),nl,
findall(N, (between(1, 6, X), N is 10^X), LimitList),
run(LimitList).
- Output:
?- do.
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
first >= 10 is 10 at position 4 [time: 0]
first >= 100 is 121 at position 11 [time: 1]
first >= 1000 is 1003 at position 74 [time: 4]
first >= 10000 is 10201 at position 242 [time: 73]
first >= 100000 is 100013 at position 2505 [time: 1442]
first >= 1000000 is 1018081 at position 10538 [time: 34054]
true.
Python
Using primesieve and numpy modules. If program is run to above 1018 it overflows 64 bit integers (that's what primesieve module backend uses internally).
from primesieve.numpy import primes
from math import isqrt
import numpy as np
max_order = 9
blocks = [primes(10**n, 10**(n + 1)) for n in range(max_order)]
def smallest_brilliant(lb):
pos = 1
root = isqrt(lb)
for blk in blocks:
n = len(blk)
if blk[-1]*blk[-1] < lb:
pos += n*(n + 1)//2
continue
i = np.searchsorted(blk, root, 'left')
i += blk[i]*blk[i] < lb
if not i:
return blk[0]*blk[0], pos
p = blk[:i + 1]
q = (lb - 1)//p
idx = np.searchsorted(blk, q, 'right')
sel = idx < n
p, idx = p[sel], idx[sel]
q = blk[idx]
sel = q >= p
p, q, idx = p[sel], q[sel], idx[sel]
pos += np.sum(idx - np.arange(len(idx)))
return np.min(p*q), pos
res = []
p = 0
for i in range(100):
p, _ = smallest_brilliant(p + 1)
res.append(p)
print(f'first 100 are {res}')
for i in range(max_order*2):
thresh = 10**i
p, pos = smallest_brilliant(thresh)
print(f'Above 10^{i:2d}: {p:20d} at #{pos}')
- Output:
first 100 are [4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299, 319, 323, 341, 361, 377, 391, 403, 407, 437, 451, 473, 481, 493, 517, 527, 529, 533, 551, 559, 583, 589, 611, 629, 649, 667, 671, 689, 697, 703, 713, 731, 737, 767, 779, 781, 793, 799, 803, 817, 841, 851, 869, 871, 893, 899, 901, 913, 923, 943, 949, 961, 979, 989, 1003, 1007, 1027, 1037, 1067, 1073, 1079, 1081, 1121, 1139, 1147, 1157, 1159, 1189, 1207, 1219, 1241, 1247, 1261, 1271, 1273, 1333, 1343, 1349, 1357, 1363, 1369] Above 10^ 0: 4 at #1 Above 10^ 1: 10 at #4 Above 10^ 2: 121 at #11 Above 10^ 3: 1003 at #74 Above 10^ 4: 10201 at #242 Above 10^ 5: 100013 at #2505 Above 10^ 6: 1018081 at #10538 Above 10^ 7: 10000043 at #124364 Above 10^ 8: 100140049 at #573929 Above 10^ 9: 1000000081 at #7407841 Above 10^10: 10000600009 at #35547995 Above 10^11: 100000000147 at #491316167 Above 10^12: 1000006000009 at #2409600866 Above 10^13: 10000000000073 at #34896253010 Above 10^14: 100000380000361 at #174155363187 Above 10^15: 1000000000000003 at #2601913448897 Above 10^16: 10000001400000049 at #13163230391313 Above 10^17: 100000000000000831 at #201431415980419
Quackery
eratosthenes and isprime are defined at Sieve of Eratosthenes#Quackery.
bsearchwith is defined at Binary search#Quackery.
[ 1 swap
[ 10 / dup iff
[ dip 1+ ]
else done
again ]
drop ] is digits ( n --> n )
[ over size 0 swap 2swap
bsearchwith < drop ] is search ( [ n --> n )
1010 eratosthenes
1 temp put
[] [] []
1010 times
[ i^ isprime if
[ temp share
i^ digits < if
[ nested join
[]
1 temp tally ]
i^ join ] ]
nested join
temp release
witheach
[ dup witheach
[ over witheach
[ over *
dip rot join unrot ]
drop behead drop ]
drop ]
sort
say "First 100 brilliant numbers:" cr
dup 100 split drop
unbuild
2 split nip -2 split drop
nest$ 40 wrap$ cr cr
6 times
[ dup dup 10 i^ 1+ **
say "First > "
dup 1 - echo
say " is "
search tuck peek echo
say " at position " 1+ echo
say "." cr ]
drop- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First > 9 is 10 at position 4. First > 99 is 121 at position 11. First > 999 is 1003 at position 74. First > 9999 is 10201 at position 242. First > 99999 is 100013 at position 2505. First > 999999 is 1018081 at position 10538.
Raku
1 through 7 are fast. 8 and 9 take a bit longer.
use Lingua::EN::Numbers;
# Find an abundance of primes to use to generate brilliants
my %primes = (2..100000).grep( &is-prime ).categorize: { .chars };
# Generate brilliant numbers
my @brilliant = lazy flat (1..*).map: -> $digits {
sort flat (^%primes{$digits}).race.map: { %primes{$digits}[$_] X× (flat %primes{$digits}[$_ .. *]) }
};
# The task
put "First 100 brilliant numbers:\n" ~ @brilliant[^100].batch(10)».fmt("%4d").join("\n") ~ "\n" ;
for 1 .. 7 -> $oom {
my $threshold = exp $oom, 10;
my $key = @brilliant.first: :k, * >= $threshold;
printf "First >= %13s is %9s in the series: %13s\n", comma($threshold), ordinal-digit(1 + $key, :u), comma @brilliant[$key];
}
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First >= 10 is 4ᵗʰ in the series: 10 First >= 100 is 11ᵗʰ in the series: 121 First >= 1,000 is 74ᵗʰ in the series: 1,003 First >= 10,000 is 242ⁿᵈ in the series: 10,201 First >= 100,000 is 2505ᵗʰ in the series: 100,013 First >= 1,000,000 is 10538ᵗʰ in the series: 1,018,081 First >= 10,000,000 is 124364ᵗʰ in the series: 10,000,043 First >= 100,000,000 is 573929ᵗʰ in the series: 100,140,049 First >= 1,000,000,000 is 7407841ˢᵗ in the series: 1,000,000,081
RPL
A fast semiprime checker was needed here.
| RPL code | Comment |
|---|---|
≪ DUP √ CEIL 0 → max div
≪ 0
2 max FOR j
WHILE OVER j MOD NOT REPEAT
SWAP j / SWAP 1 + j 'div' STO END
IF DUP 2 > THEN max 'j' STO END
NEXT
IF OVER 1 > THEN 1 + END
SWAP DROP 2 == div *
≫ ≫ ‘SPR1?’ STO
≪
IF DUP SPR1? DUP THEN
DUP2 / XPON SWAP XPON == SWAP DROP
ELSE DROP2 0 END
≫ ‘BRIL?’ STO
|
SPR1? ( n → divisor ) cnt = 0; for j = 2 to ceiling(sqrt(n)) while (n % j == 0) n /= j ; ++cnt ; div = j ; if cnt > 2 then break; if (num > 1) ++cnt; return divisor if semiprime, otherwise zero BRIL? ( n → boolean ) if semiprime then compare divisors' size else not a brilliant number |
≪ { } 1 WHILE OVER SIZE 100 < REPEAT IF DUP BRIL? THEN SWAP OVER + SWAP END 1 + END DROP ≫ EVAL
≪ { } 1 5 FOR n n ALOG WHILE DUP BRIL? NOT REPEAT 1 + END + NEXT ≫ EVAL
- Output:
2: { 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 }
1: { 10 121 1003 10201 100013 1018081 }
Rust
// [dependencies]
// primal = "0.3"
// indexing = "0.4.1"
fn get_primes_by_digits(limit: usize) -> Vec<Vec<usize>> {
let mut primes_by_digits = Vec::new();
let mut power = 10;
let mut primes = Vec::new();
for prime in primal::Primes::all().take_while(|p| *p < limit) {
if prime > power {
primes_by_digits.push(primes);
primes = Vec::new();
power *= 10;
}
primes.push(prime);
}
primes_by_digits.push(primes);
primes_by_digits
}
fn main() {
use indexing::algorithms::lower_bound;
use std::time::Instant;
let start = Instant::now();
let primes_by_digits = get_primes_by_digits(1000000000);
println!("First 100 brilliant numbers:");
let mut brilliant_numbers = Vec::new();
for primes in &primes_by_digits {
for i in 0..primes.len() {
let p1 = primes[i];
for j in i..primes.len() {
let p2 = primes[j];
brilliant_numbers.push(p1 * p2);
}
}
if brilliant_numbers.len() >= 100 {
break;
}
}
brilliant_numbers.sort();
for i in 0..100 {
let n = brilliant_numbers[i];
print!("{:4}{}", n, if (i + 1) % 10 == 0 { '\n' } else { ' ' });
}
println!();
let mut power = 10;
let mut count = 0;
for p in 1..2 * primes_by_digits.len() {
let primes = &primes_by_digits[p / 2];
let mut position = count + 1;
let mut min_product = 0;
for i in 0..primes.len() {
let p1 = primes[i];
let n = (power + p1 - 1) / p1;
let j = lower_bound(&primes[i..], &n);
let p2 = primes[i + j];
let product = p1 * p2;
if min_product == 0 || product < min_product {
min_product = product;
}
position += j;
if p1 >= p2 {
break;
}
}
println!("First brilliant number >= 10^{p} is {min_product} at position {position}");
power *= 10;
if p % 2 == 1 {
let size = primes.len();
count += size * (size + 1) / 2;
}
}
let time = start.elapsed();
println!("\nElapsed time: {} milliseconds", time.as_millis());
}
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10^1 is 10 at position 4 First brilliant number >= 10^2 is 121 at position 11 First brilliant number >= 10^3 is 1003 at position 74 First brilliant number >= 10^4 is 10201 at position 242 First brilliant number >= 10^5 is 100013 at position 2505 First brilliant number >= 10^6 is 1018081 at position 10538 First brilliant number >= 10^7 is 10000043 at position 124364 First brilliant number >= 10^8 is 100140049 at position 573929 First brilliant number >= 10^9 is 1000000081 at position 7407841 First brilliant number >= 10^10 is 10000600009 at position 35547995 First brilliant number >= 10^11 is 100000000147 at position 491316167 First brilliant number >= 10^12 is 1000006000009 at position 2409600866 First brilliant number >= 10^13 is 10000000000073 at position 34896253010 First brilliant number >= 10^14 is 100000380000361 at position 174155363187 First brilliant number >= 10^15 is 1000000000000003 at position 2601913448897 First brilliant number >= 10^16 is 10000001400000049 at position 13163230391313 First brilliant number >= 10^17 is 100000000000000831 at position 201431415980419 Elapsed time: 1515 milliseconds
Scala
val primes = 2 #:: LazyList.from(3, 2) // simple prime
.filter(p => (3 to math.sqrt(p).ceil.toInt by 2).forall(p % _ > 0))
def brilliantSemiPrimes(limit: Int): Seq[Int] = {
def iter(primeList: LazyList[Int], bLimit: Int, acc: Seq[Int]): Seq[Int] = {
val (start, tail) = (primeList.head, primeList.tail)
val brilliants = primeList
.takeWhile(_ <= bLimit)
.map(_ * start)
.takeWhile(_ <= limit)
if (brilliants.isEmpty) return acc
val bLimit1 = if (tail.head > bLimit) 10 * bLimit else bLimit
iter(tail, bLimit1, brilliants.toSeq ++ acc)
}
iter(primes, 10, Seq()).sorted
}
@main def main = {
val start = System.currentTimeMillis
val brList = brilliantSemiPrimes(1500).take(100)
val duration = System.currentTimeMillis - start
for (group <- brList.grouped(20))
println(group.map("%4d".format(_)).mkString(" "))
println(s"time elapsed: $duration ms\n")
for (limit <- (1 to 6).map(math.pow(10,_).toInt)) {
val start = System.currentTimeMillis
val (bril, index) = brilliantSemiPrimes((limit * 1.25).toInt)
.zipWithIndex
.dropWhile((b, _i) => b < limit)
.head
val duration = System.currentTimeMillis - start
println(f"first >= $limit%7d is $bril%7d at position ${index+1}%5d [time(ms) $duration%2d]")
}
}
- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 time elapsed: 3 ms first >= 10 is 10 at position 4 [time(ms) 1] first >= 100 is 121 at position 11 [time(ms) 0] first >= 1000 is 1003 at position 74 [time(ms) 1] first >= 10000 is 10201 at position 242 [time(ms) 2] first >= 100000 is 100013 at position 2505 [time(ms) 6] first >= 1000000 is 1018081 at position 10538 [time(ms) 11]
SETL
program brilliant_numbers;
init bs := brilliant(4);
print('First 100 brilliant numbers:');
loop for n in bs(1..100) do
nprint(lpad(str n, 6));
if (c +:= 1) mod 10 = 0 then
print;
end if;
end loop;
loop doing o +:= 1; while exists n = bs(i) | n >= 10**o do
print('First brilliant number >= ' + lpad(str(10**o), 10) +
': ' + lpad(str n, 10) + ' at position ' + lpad(str i,6));
end loop;
proc brilliant(orders);
primes := sieve(10**orders);
groups := group_by_digit_count(primes);
b := [];
loop for group in groups do
loop for i in [1..#group] do
loop for j in [1..i] do
b with:= group(i) * group(j);
end loop;
end loop;
end loop;
return [x : x in {x : x in b}];
end proc;
proc group_by_digit_count(nums);
magn := 10;
groups := [];
group := [];
loop for n in nums do
if n>=magn then
magn *:= 10;
groups with:= group;
group := [];
end if;
group with:= n;
end loop;
if group /= [] then
groups with:= group;
end if;
return groups;
end proc;
proc sieve(n);
ps := [True] * n;
p := 2;
loop while p*p <= n do
if ps(p) then
c := p*p;
loop while c<=n do
ps(c) := False;
c +:= p;
end loop;
end if;
p +:= 1;
end loop;
return [i : i in [2..n] | ps(i)];
end proc;
end program;- Output:
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First brilliant number >= 10: 10 at position 4
First brilliant number >= 100: 121 at position 11
First brilliant number >= 1000: 1003 at position 74
First brilliant number >= 10000: 10201 at position 242
First brilliant number >= 100000: 100013 at position 2505
First brilliant number >= 1000000: 1018081 at position 10538
First brilliant number >= 10000000: 10000043 at position 124364
Sidef
func is_briliant_number(n) {
n.is_semiprime && (n.factor.map{.len}.uniq.len == 1)
}
func brilliant_numbers_count(n) {
var count = 0
var len = n.isqrt.len
for k in (1 .. len-1) {
var pi = prime_count(10**(k-1), 10**k - 1)
count += binomial(pi, 2)+pi
}
var min = (10**(len - 1))
var max = (10**len - 1)
each_prime(min, max, {|p|
count += prime_count(p, max `min` idiv(n, p))
})
return count
}
say "First 100 brilliant numbers:"
100.by(is_briliant_number).each_slice(10, {|*a|
say a.map { '%4s' % _}.join(' ')
})
say ''
for n in (1 .. 12) {
var v = (10**n .. Inf -> first_by(is_briliant_number))
printf("First brilliant number >= 10^%d is %s", n, v)
printf(" at position %s\n", brilliant_numbers_count(v))
}
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10^1 is 10 at position 4 First brilliant number >= 10^2 is 121 at position 11 First brilliant number >= 10^3 is 1003 at position 74 First brilliant number >= 10^4 is 10201 at position 242 First brilliant number >= 10^5 is 100013 at position 2505 First brilliant number >= 10^6 is 1018081 at position 10538 First brilliant number >= 10^7 is 10000043 at position 124364 First brilliant number >= 10^8 is 100140049 at position 573929 First brilliant number >= 10^9 is 1000000081 at position 7407841 First brilliant number >= 10^10 is 10000600009 at position 35547995 First brilliant number >= 10^11 is 100000000147 at position 491316167 First brilliant number >= 10^12 is 1000006000009 at position 2409600866
Swift
Magnitudes of 1 to 3 is decent, 4 and beyond becomes slow.
// Refs:
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/?ref=leftbar-rightbar
// https://developer.apple.com/documentation/swift/array/init(repeating:count:)-5zvh4
// https://www.geeksforgeeks.org/brilliant-numbers/#:~:text=Brilliant%20Number%20is%20a%20number,25%2C%2035%2C%2049%E2%80%A6.
// Using Sieve of Eratosthenes
func primeArray(n: Int) -> [Bool] {
var primeArr = [Bool](repeating: true, count: n + 1)
primeArr[0] = false // setting zero to be not prime
primeArr[1] = false // setting one to be not prime
// finding all primes which are divisible by p and are greater than or equal to the square of it
var p = 2
while (p * p) <= n {
if primeArr[p] == true {
for j in stride(from: p * 2, through: n, by: p) {
primeArr[j] = false
}
}
p += 1
}
return primeArr
}
func digitsCount(n: Int) -> Int {
// count number of digits for a number
// increase the count if n divide by 10 is not equal to zero
var num = n
var count = 0;
while num != 0 {
num = num/10
count += 1
}
return count
}
func isBrilliant(n: Int) -> Bool {
// Set the prime array
var isPrime = [Bool]()
isPrime = primeArray(n: n)
// Check if the number is the product of two prime numbers
// Also check if the digit counts of those prime numbers are the same.
for i in stride(from: 2, through: n, by: 1) { // i=2, n=50
let x = n / i // i=2, n=50, x=25
if (isPrime[i] && isPrime[x] && x * i == n) { // i=2, x=50, false
if (digitsCount(n: i) == digitsCount(n: x)) {
return true
}
}
}
return false
}
func print100Brilliants() {
// Print the first 100 brilliant numbers
var brilNums = [Int]()
var count = 4
while brilNums.count != 100 {
if isBrilliant(n: count) {
brilNums.append(count)
}
count += 1
}
print("First 100 brilliant numbers:\n", brilNums)
}
func printBrilliantsOfMagnitude() {
// Print the brilliant numbers of base 10 up to magnitude of 6
// Including their positions in the array.
var basePower = 10.0
var brilNums: [Double] = [0.0]
var count = 1.0
while basePower != pow(basePower, 6) {
if isBrilliant(n: Int(count)) {
brilNums.append(count)
if count >= basePower {
print("First brilliant number >= \(Int(basePower)): \(Int(count)) at position \(brilNums.firstIndex(of: count)!)")
basePower *= 10
}
}
count += 1
}
}
print100Brilliants()
printBrilliantsOfMagnitude()
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First brilliant number >= 10: 10 at position 4 First brilliant number >= 100: 121 at position 11 First brilliant number >= 1000: 1003 at position 74 First brilliant number >= 10000: 10201 at position 242 First brilliant number >= 100000: 100013 at position 2505 First brilliant number >= 1000000: 1018081 at position 10538
Wren
import "./math" for Int
import "./fmt" for Fmt
var primes = Int.primeSieve(1e7-1)
var getBrilliant = Fn.new { |digits, limit, countOnly|
var brilliant = []
var count = 0
var pow = 1
var next = Num.maxSafeInteger
for (k in 1..digits) {
var s = primes.where { |p| p > pow && p < pow * 10 }.toList
for (i in 0...s.count) {
for (j in i...s.count) {
var prod = s[i] * s[j]
if (prod < limit) {
if (countOnly) {
count = count + 1
} else {
brilliant.add(prod)
}
} else {
next = next.min(prod)
break
}
}
}
pow = pow * 10
}
return countOnly ? [count, next] : [brilliant, next]
}
System.print("First 100 brilliant numbers:")
var brilliant = getBrilliant.call(2, 10000, false)[0]
brilliant.sort()
brilliant = brilliant[0..99]
Fmt.tprint("$4d", brilliant, 10)
System.print()
for (k in 1..12) {
var limit = 10.pow(k)
var res = getBrilliant.call(k, limit, true)
var total = res[0]
var next = res[1]
Fmt.print("First >= $,17d is $,15r in the series: $,17d", limit, total + 1, next)
}
- Output:
First 100 brilliant numbers: 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First >= 10 is 4th in the series: 10 First >= 100 is 11th in the series: 121 First >= 1,000 is 74th in the series: 1,003 First >= 10,000 is 242nd in the series: 10,201 First >= 100,000 is 2,505th in the series: 100,013 First >= 1,000,000 is 10,538th in the series: 1,018,081 First >= 10,000,000 is 124,364th in the series: 10,000,043 First >= 100,000,000 is 573,929th in the series: 100,140,049 First >= 1,000,000,000 is 7,407,841st in the series: 1,000,000,081 First >= 10,000,000,000 is 35,547,995th in the series: 10,000,600,009 First >= 100,000,000,000 is 491,316,167th in the series: 100,000,000,147 First >= 1,000,000,000,000 is 2,409,600,866th in the series: 1,000,006,000,009
XPL0
func NumDigits(N); \Return number of digits in N
int N, Cnt;
[Cnt:= 0;
repeat N:= N/10;
Cnt:= Cnt+1;
until N = 0;
return Cnt;
];
func Brilliant(N); \Return 'true' if N is a brilliant number
int N, Limit, Cnt, F;
int A(3);
[Limit:= sqrt(N);
Cnt:= 0; F:= 2;
loop [if rem(N/F) = 0 then
[A(Cnt):= F;
Cnt:= Cnt+1;
if Cnt > 2 then quit;
N:= N/F;
]
else F:= F+1;
if F > N then quit;
if F > Limit then
[A(Cnt):= N;
Cnt:= Cnt+1;
quit;
];
];
if Cnt # 2 then return false;
return NumDigits(A(0)) = NumDigits(A(1));
];
int Cnt, N, Mag;
[Format(5, 0);
Cnt:= 0; N:= 4;
loop [if Brilliant(N) then
[RlOut(0, float(N));
Cnt:= Cnt+1;
if Cnt >= 100 then quit;
if rem(Cnt/10) = 0 then CrLf(0);
];
N:= N+1;
];
CrLf(0); CrLf(0);
Format(7, 0);
Cnt:= 0; N:= 4; Mag:= 10;
loop [if Brilliant(N) then
[Cnt:= Cnt+1;
if N >= Mag then
[Text(0, "First >= ");
RlOut(0, float(Mag));
Text(0, " is ");
RlOut(0, float(Cnt));
Text(0, " in series: ");
RlOut(0, float(N));
CrLf(0);
if Mag >= 1_000_000 then quit;
Mag:= Mag*10;
];
];
N:= N+1;
];
]- Output:
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 First >= 10 is 4 in series: 10 First >= 100 is 11 in series: 121 First >= 1000 is 74 in series: 1003 First >= 10000 is 242 in series: 10201 First >= 100000 is 2505 in series: 100013 First >= 1000000 is 10538 in series: 1018081
Categories:
- Programming Tasks
- Solutions by Programming Task
- Ada
- ALGOL 68
- ALGOL 68-primes
- AppleScript
- Arturo
- C++
- Primesieve
- Delphi
- SysUtils,StdCtrls
- EasyLang
- Factor
- FreeBASIC
- FutureBasic
- Go
- Go-rcu
- Haskell
- J
- Java
- Jq
- Julia
- Mathematica
- Wolfram Language
- Nim
- Perl
- Ntheory
- Phix
- Phix/online
- Prolog
- Python
- Quackery
- Raku
- RPL
- Rust
- Scala
- SETL
- Sidef
- Swift
- Wren
- Wren-math
- Wren-fmt
- XPL0