Anaprimes: Difference between revisions
Content deleted Content added
→{{header|ALGOL 68}}: typo |
|||
(14 intermediate revisions by 9 users not shown) | |||
Line 1:
{{
Anaprimes are prime numbers that are anagrams of each other, i.e. they use exactly the same digits with the same frequency but in a different order.
Line 33:
=={{header|ALGOL 68}}==
If running this with Algol 68G, a large heap size must be requested on the command line with, e.g.: <code>-heap 512M</code> for version 2 under Windows. On TIO.RUN, it wanted <code>-heap=512M</code>. If max prime is set to 100 000 000, the heap size needs to be 1536M (which I think is thge largest size Algol 68G allows).
<syntaxhighlight lang="algol68">
BEGIN # find some anaprimes: groups of primes that have the same digits and #
Line 234:
First: 1,123,465,789 Last: 9,876,543,211
</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang=text>
fastfunc isprim num .
if num mod 2 = 0
if num = 2
return 1
.
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
fastfunc nextprim prim .
repeat
prim += 1
until isprim prim = 1
.
return prim
.
func group n .
while n > 0
d = n mod 10
n = n div 10
h = pow 10 d
r += h
.
return r
.
hashsz = 199999
len hashind[] hashsz
len hashval[] hashsz
global maxcnt grcnt[] grmax[] grmin[] .
#
func hash ind .
hi = ind mod hashsz + 1
while hashind[hi] <> 0 and hashind[hi] <> ind
hi = hi mod hashsz + 1
.
return hi
.
prim = 1
for limit in [ 1000 10000 100000 1000000 ]
repeat
prim = nextprim prim
until prim >= limit
g = group prim
hi = hash g
if hashind[hi] = 0
hashind[hi] = g
grcnt[] &= 1
grmax[] &= prim
grmin[] &= prim
hashval[hi] = len grcnt[]
else
i = hashval[hi]
grcnt[i] += 1
grmax[i] = higher grmax[i] prim
grmin[i] = lower grmin[i] prim
maxcnt = higher grcnt[i] maxcnt
.
.
print maxcnt
for i to len grcnt[]
if grcnt[i] = maxcnt
print grmin[i] & " " & grmax[i]
.
.
print ""
.
</syntaxhighlight>
{{out}}
<pre>
4
149 941
179 971
379 937
11
1237 7321
1279 9721
39
13789 98731
148
123479 974213
</pre>
Line 258 ⟶ 352:
9 digits: Count=26519 Min=102345697 Max=976542103
</pre>
=={{header|Go}}==
{{trans|Wren}}
Line 407 ⟶ 502:
'''General utilities'''
<syntaxhighlight lang=jq>
# Input: a positive integer
#
# $a[$i] is $i if $i is prime, and false otherwise.
def primeSieve:
# erase(i) sets .[i*j] to false for integral j > 1
def erase($i):
if .[$i] then
reduce (range(2*$i;
else .
end;
Line 521 ⟶ 617:
For 10-digit primes, a largest anagram group, [1123465789, ..9876543211], has a group size of 152526.
186.920326 seconds (455.94 M allocations: 72.961 GiB, 1.54% gc time, 0.02% compilation time)
</pre>
=={{header|Nim}}==
{{trans|Wren}}
Run in 14 seconds on an Intel Core i5-8250U (four cores at 1.60GHz).
<syntaxhighlight lang="Nim">import std/[algorithm, bitops, math, strformat, strutils, tables]
type Sieve = object
data: seq[byte]
func `[]`(sieve: Sieve; idx: Positive): bool =
## Return value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
func newSieve(lim: Positive): Sieve =
## Create a sieve with given maximal index.
result.data = newSeq[byte]((lim + 16) shr 4)
func initPrimes(lim: Positive): seq[Natural] =
## Initialize the list of primes from 2 to "lim".
var composite = newSieve(lim)
composite[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, lim, 2 * n):
composite[k] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n]:
result.add n
proc digits(n: Positive): seq[0..9] =
var n = n.Natural
while n != 0:
result.add n mod 10
n = n div 10
const Limit = 1_000_000_000
const MaxIndex = log10(Limit.toFloat).int
let primes = initPrimes(Limit)
var anaPrimes: Table[int, seq[int]]
for p in primes:
var key = 1
for digit in p.digits:
key *= primes[digit]
anaPrimes.mgetOrPut(key, @[]).add p
var largest: array[1..MaxIndex, int]
var groups: array[1..MaxIndex, seq[seq[int]]]
for key, values in anaPrimes.pairs:
let nd = values[0].digits.len
if values.len > largest[nd]:
largest[nd] = values.len
groups[nd] = @[values]
elif values.len == largest[nd]:
groups[nd].add values
var j = 1000
for i in 3..MaxIndex:
echo &"Largest group(s) of anaprimes before {insertSep($j)}: {largest[i]} members:"
groups[i].sort(proc (x, y: seq[int]): int = cmp(x[0], y[0]))
for g in groups[i]:
echo &" First: {insertSep($g[0])} Last: {insertSep($g[^1])}"
j *= 10
echo()
</syntaxhighlight>
{{out}}
<pre>Largest group(s) of anaprimes before 1_000: 4 members:
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group(s) of anaprimes before 10_000: 11 members:
First: 1_237 Last: 7_321
First: 1_279 Last: 9_721
Largest group(s) of anaprimes before 100_000: 39 members:
First: 13_789 Last: 98_731
Largest group(s) of anaprimes before 1_000_000: 148 members:
First: 123_479 Last: 974_213
Largest group(s) of anaprimes before 10_000_000: 731 members:
First: 1_235_789 Last: 9_875_321
Largest group(s) of anaprimes before 100_000_000: 4333 members:
First: 12_345_769 Last: 97_654_321
Largest group(s) of anaprimes before 1_000_000_000: 26519 members:
First: 102_345_697 Last: 976_542_103
</pre>
Line 820 ⟶ 1,019:
real 4m19.653s user 4m17.515s sys 0m2.134s</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36;
use ntheory 'primes';
use List::Util 'max';
use Lingua::EN::Numbers qw(num2en);
for my $l (3..9) {
my %p;
$p{ join '', sort split //, "$_" } .= "$_ " for @{ primes 10**($l-1), 10**$l };
my $m = max map { length $p{$_} } keys %p;
printf "Largest group of anaprimes before %s: %d members.\n", num2en(10**$l), $m/($l+1);
for my $k (sort grep { $m == length $p{$_} } keys %p) {
printf "First: %d Last: %d\n", $p{$k} =~ /^(\d+).* (\d+) $/;
}
say '';
}</syntaxhighlight>
{{out}}
<pre>Largest group of anaprimes before one thousand: 4 members.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group of anaprimes before ten thousand: 11 members.
First: 1237 Last: 7321
First: 1279 Last: 9721
Largest group of anaprimes before one hundred thousand: 39 members.
First: 13789 Last: 98731
Largest group of anaprimes before one million: 148 members.
First: 123479 Last: 974213
Largest group of anaprimes before ten million: 731 members.
First: 1235789 Last: 9875321
Largest group of anaprimes before one hundred million: 4333 members.
First: 12345769 Last: 97654321
Largest group of anaprimes before one billion: 26519 members.
First: 102345697 Last: 976542103</pre>
=={{header|Phix}}==
Line 899 ⟶ 1,140:
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers;
use Math::Primesieve;
use List::Allmax;
my $p = Math::Primesieve.new;
for 3 .. 9 {
my
put "\nLargest group of anaprimes before {cardinal 10 ** $_}: {+
put 'First: ', ' Last: ' Z~
}</syntaxhighlight>
{{out}}
<pre>Largest group of anaprimes before one thousand: 4 members.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group of anaprimes before ten thousand: 11 members.
First: 1237 Last: 7321
First: 1279 Last: 9721
Largest group of anaprimes before one hundred thousand: 39 members.
Line 929 ⟶ 1,174:
Largest group of anaprimes before one billion: 26,519 members.
First: 102345697 Last: 976542103</pre>
=={{header|Ruby}}==
9 digit takes about 4 minutes (not done here). Could use something like Raku's Allmax.
<syntaxhighlight lang="ruby" line>require 'prime'
upto = 100_000_000
h = Hash.new {|hash, key| hash[key] = []}
Prime.each(upto) {|pr| h[pr.digits.sort] << pr }
(3..(upto.digits.size-1)).each do |num_digits|
group = h.select {|k,v| k.size == num_digits}
sizes = group.values.group_by(&:size)
max = sizes.keys.max
maxes = sizes[max]
puts "Anaprime groups of #{num_digits} digits: #{maxes.size} ha#{maxes.size == 1 ? "s" : "ve"} #{max} primes."
maxes.each{|group| puts " First: #{group.first} Last: #{group.last}"}
end
</syntaxhighlight>
{{out}}
<pre>Anaprime groups of 3 digits: 3 have 4 primes.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Anaprime groups of 4 digits: 2 have 11 primes.
First: 1237 Last: 7321
First: 1279 Last: 9721
Anaprime groups of 5 digits: 1 has 39 primes.
First: 13789 Last: 98731
Anaprime groups of 6 digits: 1 has 148 primes.
First: 123479 Last: 974213
Anaprime groups of 7 digits: 1 has 731 primes.
First: 1235789 Last: 9875321
Anaprime groups of 8 digits: 1 has 4333 primes.
First: 12345769 Last: 97654321</pre>
=={{header|Sidef}}==
Up to 8 digits, takes about 30 seconds, using ~800 MB of RAM.
<syntaxhighlight lang="ruby">for k in (3..8) {
var P = primes(10**(k-1), 10**k).group_by{ Str(_).sort }
var G = P.values
var m = G.map{.len}.max
printf("Largest group of anaprimes before %s: %s members.\n", commify(10**k), m)
G.grep { .len == m }.sort.each {|group|
say "First: #{group.head} Last: #{group.tail}"
}
say ""
}</syntaxhighlight>
{{out}}
<pre>
Largest group of anaprimes before 1,000: 4 members.
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
Largest group of anaprimes before 10,000: 11 members.
First: 1237 Last: 7321
First: 1279 Last: 9721
Largest group of anaprimes before 100,000: 39 members.
First: 13789 Last: 98731
Largest group of anaprimes before 1,000,000: 148 members.
First: 123479 Last: 974213
Largest group of anaprimes before 10,000,000: 731 members.
First: 1235789 Last: 9875321
Largest group of anaprimes before 100,000,000: 4333 members.
First: 12345769 Last: 97654321
</pre>
=={{header|Wren}}==
Line 934 ⟶ 1,249:
{{libheader|Wren-fmt}}
Getting up to 1 billion takes around 2 minutes 25 seconds on my Core i7 machine. I've left it at that.
<syntaxhighlight lang="
import "./fmt" for Fmt
|