Brilliant numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
(julia example)
Line 73: Line 73:


Note that we have avoided coding for the issue where index 0 gets the first element of the list by displaying the order of magnitude and the first brilliant value of that order of magnitude.
Note that we have avoided coding for the issue where index 0 gets the first element of the list by displaying the order of magnitude and the first brilliant value of that order of magnitude.

=={{header|Julia}}==
<lang 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, floors, results, positions = 0, zeros(Int, 9), 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
end

testbrilliants()
<lang>{{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 >= 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
</pre>


=={{header|Phix}}==
=={{header|Phix}}==

Revision as of 02:48, 25 February 2022

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

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>

Note that we have avoided coding for the issue where index 0 gets the first element of the list by displaying the order of magnitude and the first brilliant value of that order of magnitude.

Julia

<lang 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, floors, results, positions = 0, zeros(Int, 9), 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

end

testbrilliants()

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

Phix

Translation of: Wren
Library: Phix/online

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;

  1. Find an abundance of primes to use to generate brilliants

my %primes = (2..100000).grep( &is-prime ).categorize: { .chars };

  1. Generate brilliant numbers

my @brilliant = lazy flat (1..*).map: -> $digits { 

   sort flat (^%primes{$digits}).race.map: { %primes{$digits}[$_] X× (flat %primes{$digits}[$_ .. *]) }

};

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

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt

<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
Retrieved from "https://rosettacode.org/wiki/Brilliant_numbers?oldid=319869"