Brilliant numbers: Difference between revisions
Added Easylang
(→{{header|Python}}: change to numpy for efficiency) |
(Added Easylang) |
||
| (30 intermediate revisions by 14 users not shown) | |||
Line 27:
;* [https://www.numbersaplenty.com/set/brilliant_number Numbers Aplenty - Brilliant numbers]
;* [[oeis:A078972|OEIS:A078972 - Brilliant numbers: semiprimes whose prime factors have the same number of decimal digits]]
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
<
# the same number of digits #
PR read "primes.incl.a68" PR # include prime utilities #
Line 86 ⟶ 83:
FI
OD
END</
{{out}}
<pre>
Line 106 ⟶ 103:
First brilliant number >= 1000000: 1018081 at position 10538
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="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()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"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"</syntaxhighlight>
=={{header|Arturo}}==
<
pf: factors.prime x
and? -> 2 = size pf
Line 142 ⟶ 290:
i: i + 1
]</
{{out}}
Line 164 ⟶ 312:
First brilliant number >= 10 ^ 5 is 100013 at position 2505
First brilliant number >= 10 ^ 6 is 1018081 at position 10538</pre>
=={{header|C++}}==
{{libheader|Primesieve}}
<
#include <chrono>
#include <iomanip>
Line 180 ⟶ 327:
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) {
Line 245 ⟶ 392:
std::chrono::duration<double> duration(end - start);
std::cout << "\nElapsed time: " << duration.count() << " seconds\n";
}</
{{out}}
Line 276 ⟶ 423:
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:
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="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;
</syntaxhighlight>
{{out}}
<pre>
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.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
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
</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
<
math math.functions math.primes.factors prettyprint
project-euler.common sequences ;
Line 302 ⟶ 633:
100 lbrilliant ltake list>array keys 10 group simple-table. nl
{ 1 2 3 4 5 6 } [ 10^ .first> ] each</
{{out}}
<pre>
Line 323 ⟶ 654:
First brilliant number >= 1000000: 1018081 at position 10538
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="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
</syntaxhighlight>
<pre>
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
</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<
import (
Line 405 ⟶ 814:
fmt.Printf("First >= %18s is %14s in the series: %18s\n", climit, ctotal, cnext)
}
}</
{{out}}
Line 436 ⟶ 845:
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{Out}}
<pre> 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)</pre>
=={{header|J}}==
<
p:(+i.)/-/\ p:inv +/\1 9*10^y
}}
Line 448 ⟶ 920:
brillseq=: {{ NB. sequences of brilliant numbers up through order y-1 primes
/:~;obrill each i.y
}}</
Task examples:
<
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
Line 470 ⟶ 942:
4 241 10201
5 2504 100013
6 10537 1018081</
Stretch goal (results are order, index, value):
<
7 124363 10000043
(brillseq 5) (],.(I. 10^]) ([,.{) [) 8 9
8 573928 100140049
9 7407840 1000000081</
=={{header|Java}}==
{{trans|C++}}
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
<
public class BrilliantNumbers {
public static void main(String[] args) {
var primesByDigits = getPrimesByDigits(
System.out.println("First 100 brilliant numbers:");
List<Integer> brilliantNumbers = new ArrayList<>();
Line 545 ⟶ 1,016:
List<List<Integer>> primesByDigits = new ArrayList<>();
List<Integer> primes = new ArrayList<>();
for (int p = 10; p <= limit; ) {
int prime = primeGen.nextPrime();
if (prime > p) {
Line 556 ⟶ 1,027:
return primesByDigits;
}
}</
{{out}}
Line 587 ⟶ 1,058:
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
</pre>
=={{header|jq}}==
{{works with|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]].
<syntaxhighlight lang=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)
</syntaxhighlight>
{{output}}
<pre>
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]
</pre>
=={{header|Julia}}==
<
using Primes
Line 621 ⟶ 1,170:
testbrilliants()
</
<pre>
First 100 brilliant numbers:
Line 641 ⟶ 1,190:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
PrimesDecade[n_Integer] := Module[{bounds},
bounds = {PrimePi[10^n] + 1, PrimePi[10^(n + 1) - 1]};
Line 651 ⟶ 1,200:
sel = Min /@ GatherBy[Select[ds, GreaterEqualThan[10]], IntegerLength];
Grid[{#, FirstPosition[ds, #][[1]]} & /@ sel]</
{{out}}
<pre>4 6 9 10 14 15 21 25
Line 676 ⟶ 1,225:
100140049 573929
1000000081 7407841</pre>
=={{header|Nim}}==
{{trans|C++}}
{{trans|Java}}
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
Most of the execution time is used to fill the sieve of Erathostenes.
<pre>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
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<
use warnings;
use feature 'say';
Line 700 ⟶ 1,352:
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];
}</
{{out}}
<pre>First 100 brilliant numbers:
Line 726 ⟶ 1,378:
=== Faster approach ===
{{trans|Sidef}}
<
use strict;
use warnings;
Line 795 ⟶ 1,447:
printf("First brilliant number >= 10^%d is %s", $n, $v);
printf(" at position %s\n", brilliant_numbers_count($v));
}</
{{out}}
<pre>
Line 824 ⟶ 1,476:
First brilliant number >= 10^13 is 10000000000073 at position 34896253010
</pre>
=={{header|Phix}}==
{{trans|C++}}
Line 830 ⟶ 1,481:
Replaced with C++ translation; much faster and now goes comfortably to 1e15 even on 32 bit.
You can run this online [http://phix.x10.mx/p2js/brilliant.htm here].
<!--<
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\BrilliantNumbers.exw
Line 898 ⟶ 1,549:
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</
{{out}}
<pre>
Line 930 ⟶ 1,581:
First brilliant number >= 10^15 is 1,000,000,000,000,003 at position 2,601,913,448,897
"3.3s"
</pre>
=={{header|Prolog}}==
works with swi-prolog
<syntaxhighlight lang="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).
</syntaxhighlight>
{{out}}
<pre>?- 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.
</pre>
=={{header|Python}}==
Using primesieve and numpy modules. If program is run to above 10<sup>18</sup> it overflows 64 bit integers (that's what primesieve module backend uses internally).
<
from math import isqrt
import numpy as np
max_order = 9
def smallest_brilliant(lb):
Line 946 ⟶ 1,678:
root = isqrt(lb)
for blk in
n = len(blk)
if blk[-1]*blk[-1] < lb:
Line 983 ⟶ 1,715:
thresh = 10**i
p, pos = smallest_brilliant(thresh)
print(f'Above 10^{i:2d}: {p:20d} at #{pos}')</
{{out}}
<pre>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]
Line 1,004 ⟶ 1,736:
Above 10^16: 10000001400000049 at #13163230391313
Above 10^17: 100000000000000831 at #201431415980419</pre>
=={{header|Quackery}}==
<code>eratosthenes</code> and <code>isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]].
<code>bsearchwith</code> is defined at [[Binary search#Quackery]].
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>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.</pre>
=={{header|Raku}}==
1 through 7 are fast. 8 and 9 take a bit longer.
<syntaxhighlight lang="raku"
# Find an abundance of primes to use to generate brilliants
Line 1,024 ⟶ 1,832:
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];
}</
{{out}}
<pre>First 100 brilliant numbers:
Line 1,047 ⟶ 1,855:
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</pre>
=={{header|RPL}}==
A fast semiprime checker was needed here.
{| class="wikitable" ≪
! 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 *
≫ ≫ ‘<span style="color:blue">SPR1?</span>’ STO
≪
'''IF''' DUP <span style="color:blue">SPR1?</span> DUP '''THEN'''
DUP2 / XPON SWAP XPON == SWAP DROP
'''ELSE''' DROP2 0 '''END'''
≫ ‘<span style="color:blue">BRIL?</span>’ STO
|
<span style="color:blue">SPR1?</span> ''( 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
<span style="color:blue">BRIL?</span> ''( n → boolean ) ''
if semiprime then
compare divisors' size
else not a brilliant number
|}
≪ { } 1 '''WHILE''' OVER SIZE 100 < '''REPEAT''' '''IF''' DUP <span style="color:blue">BRIL?</span> '''THEN''' SWAP OVER + SWAP '''END''' 1 + '''END''' DROP ≫ EVAL
≪ { } 1 5 '''FOR''' n n ALOG '''WHILE''' DUP <span style="color:blue">BRIL?</span> NOT '''REPEAT''' 1 + '''END''' + '''NEXT''' ≫ EVAL
{{out}}
<pre>
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 }
</pre>
=={{header|Rust}}==
{{trans|C++}}
<
// primal = "0.3"
// indexing = "0.4.1"
Line 1,066 ⟶ 1,922:
primes.push(prime);
}
primes_by_digits.push(primes);
primes_by_digits
}
Line 1,128 ⟶ 1,985:
let time = start.elapsed();
println!("\nElapsed time: {} milliseconds", time.as_millis());
}</
{{out}}
Line 1,159 ⟶ 2,016:
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:
</pre>
=={{header|Scala}}==
<syntaxhighlight lang="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]")
}
}
</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
=={{header|Sidef}}==
<
n.is_semiprime && (n.factor.map{.len}.uniq.len == 1)
}
Line 1,200 ⟶ 2,113:
printf("First brilliant number >= 10^%d is %s", n, v)
printf(" at position %s\n", brilliant_numbers_count(v))
}</
{{out}}
<pre>
Line 1,228 ⟶ 2,141:
First brilliant number >= 10^12 is 1000006000009 at position 2409600866
</pre>
=={{header|Swift}}==
Magnitudes of 1 to 3 is decent, 4 and beyond becomes slow.
<
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/?ref=leftbar-rightbar
// https://developer.apple.com/documentation/swift/array/init(repeating:count:)-5zvh4
Line 1,327 ⟶ 2,239:
print100Brilliants()
printBrilliantsOfMagnitude()</
{{out}}
Line 1,352 ⟶ 2,264:
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
Line 1,391 ⟶ 2,301:
brilliant.sort()
brilliant = brilliant[0..99]
Fmt.tprint("$4d", brilliant, 10)
System.print()
for (k in 1..12) {
Line 1,399 ⟶ 2,309:
var next = res[1]
Fmt.print("First >= $,17d is $,15r in the series: $,17d", limit, total + 1, next)
}</
{{out}}
Line 1,430 ⟶ 2,340:
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">
func NumDigits(N); \Return number of digits in N
int N, Cnt;
Line 1,493 ⟶ 2,403:
N:= N+1;
];
]</
{{out}}
| |||