Brilliant numbers: Difference between revisions
(J) |
|||
Line 29: | Line 29: | ||
=={{header|J}}== |
|||
<lang 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 |
|||
}}</lang> |
|||
Task examples: |
|||
<lang J> 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 |
|||
(brillseq 4) (],.(I. 10^]) { [) 1 2 3 4 5 6 |
|||
1 10 |
|||
2 121 |
|||
3 1003 |
|||
4 10201 |
|||
5 100013 |
|||
6 1018081</lang> |
|||
Stretch goal: |
|||
<lang J> (brillseq 4) (],.(I. 10^]) { [) 7 |
|||
7 10000043 |
|||
(brillseq 5) (],.(I. 10^]) { [) 8 9 |
|||
8 100140049 |
|||
9 1000000081</lang> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
Revision as of 23:22, 24 February 2022
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
J
<lang 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
}}</lang>
Task examples:
<lang J> 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
(brillseq 4) (],.(I. 10^]) { [) 1 2 3 4 5 6
1 10 2 121 3 1003 4 10201 5 100013 6 1018081</lang>
Stretch goal: <lang J> (brillseq 4) (],.(I. 10^]) { [) 7 7 10000043
(brillseq 5) (],.(I. 10^]) { [) 8 9
8 100140049 9 1000000081</lang>
Phix
You can run this online here.
with javascript_semantics constant primes = get_primes_le(1e5-1) function get_brilliant(integer digits, limit, bool countOnly=false) sequence brilliant = {} integer count = 0, start = 1 atom pow = 10 for k=1 to digits do integer finish = abs(binary_search(pow,primes))-1 for i=start to finish do for j=i to finish do atom prod = primes[i] * primes[j] if prod>=limit then exit end if if countOnly then count += 1 else brilliant &= prod end if end for end for start = finish+1 pow *= 10 end for return iff(countOnly?count:brilliant) end function sequence b100 = sort(get_brilliant(2,10000))[1..100], s100 = apply(true,sprintf,{{"%4d"},b100}), j100 = join_by(s100,1,10," ") printf(1,"First 100 brilliant numbers:\n%s\n",{j100}) for k=1 to 9 do integer limit = power(10,k), total = get_brilliant(k, limit, true)+1, i = limit+(k!=1) while true do sequence f = prime_factors(i,true,-1) if length(f)=2 and length(sprint(f[1]))=length(sprint(f[2])) then exit end if i += 1+(k!=1) end while printf(1,"First >= %,13d is %,11d%s in the series: %,13d\n", {limit, total, ord(total), i}) end for
- 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
Raku
1 through 7 are fast. 8 and 9 take a bit longer. <lang perl6>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];
}</lang>
- 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
Wren
<lang ecmascript>import "./math" for Int import "./seq" for Lst import "./fmt" for Fmt
var primes = Int.primeSieve(1e5-1)
var getBrilliant = Fn.new { |digits, limit, countOnly|
var brilliant = [] var count = 0 var pow = 1 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 break } } pow = pow * 10 } return countOnly ? count : brilliant
}
System.print("First 100 brilliant numbers:") var brilliant = getBrilliant.call(2, 10000, false) brilliant.sort() brilliant = brilliant[0..99] for (chunk in Lst.chunks(brilliant, 10)) Fmt.print("$4d", chunk) System.print() for (k in 1..9) {
var limit = 10.pow(k) var total = getBrilliant.call(k, limit, true) var i = (k == 1) ? limit : limit + 1 while (true) { var factors = Int.primeFactors(i) if (factors.count == 2) { if (factors[0].toString.count == factors[1].toString.count) break } i = (k == 1) ? i + 1: i + 2 } Fmt.print("First >= $,13d is $,11r in the series: $,13d", limit, total + 1, i)
}</lang>
- 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