Pan base non-primes: Difference between revisions
m (→{{header|Julia}}: cleanup) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 53:
=={{header|ALGOL 68}}==
{{Trans|Wren}}
<
PR read "primes.incl.a68" PR # include prime utilities #
INT limit = 2500;
Line 150:
)
)
END</
{{out}}
<pre>
Line 170:
=={{header|J}}==
Implementation:<
digits=. 10 #.inv y
*/0=1 p: ((>./digits)+i.y) #."0 1 digits
}}"0</
Task examples:<
1 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100
20{.(#~ 2&|)1+I.pbnp 1+i.1e3 NB. first 20 odd pan based non primes
Line 183:
64
100*(+/%#)2|1+I.pbnp 1+i.1e3 NB. percent odd pan based non primes up to 1000
16.9761</
=={{header|Julia}}==
<
ispanbasecomposite(n) = (d = digits(n); all(b -> !isprime(evalpoly(b, d)), maximum(d)+1:max(10, n)))
Line 204:
println("Odd up to and including 2500: ", ratio, ", or ", Float16(ratio * 100), "%.")
println("Even up to and including 2500: ", 1 - ratio, ", or ", Float16((1.0 - ratio) * 100), "%.")
</
<pre>
First 50 pan base non-primes:
Line 224:
=={{header|Pascal}}==
==={{header|Free Pascal}}===
<
program PanBaseNonPrime;
// Check Pan-Base Non-Prime
Line 452:
END.
</syntaxhighlight>
{{out}}
<pre>
Line 473:
=={{header|Phix}}==
{{trans|Wren}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2500</span>
Line 509:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Number odd = %3d or %9.6f%%\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">oc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">oc</span><span style="color: #0000FF;">/</span><span style="color: #000000;">tc</span><span style="color: #0000FF;">*</span><span style="color: #000000;">100</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Number even = %3d or %9.6f%%\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ec</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ec</span><span style="color: #0000FF;">/</span><span style="color: #000000;">tc</span><span style="color: #0000FF;">*</span><span style="color: #000000;">100</span><span style="color: #0000FF;">})</span>
<!--</
Output same as Wren
=={{header|Raku}}==
<syntaxhighlight lang="raku"
use List::Divvy;
Line 525:
put "Percent odd up to and including $threshold: " ~ +@np.&upto($threshold).grep(* % 2) / +@np.&upto($threshold) × 100;
put "Percent even up to and including $threshold: " ~ +@np.&upto($threshold).grep(* %% 2) / +@np.&upto($threshold) × 100;</
{{out}}
<pre>First 50 pan-base composites:
Line 545:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
Line 588:
var c
Fmt.print("Number odd = $3d or $9.6f\%", c = odd.count, c/tc * 100)
Fmt.print("Number even = $3d or $9.6f\%", c = tc - c, c/tc * 100) </
{{out}}
|
Revision as of 00:46, 28 August 2022
Primes are prime no matter which base they are expressed in. Some numeric strings are prime in a large number of bases. (Not the same prime, but a prime.)
- For example
The numeric string "255", while obviously not a prime in base 10, is a prime in bases:
6 8 12 14 18 24 26 32 36 38 72 84 86 92 96 102 104 108 128 134 138 144 158 164 188 216 224 236 242 246 252 254 264 272 294 318 332 344 348 368 374 392 396 408 428 432 446 456 468 476 482 512 522 528 542 546 552 566 572 576 578 594 596 602 606 614 618 626 654 702 714 722 728 756 762 774 776 788 806 816 818 822 828 836 848 864 866 872 882 888 902 908 912 918 924 932 936 942 944 956 966 986 998
among others.
There are numeric strings however, that are not a prime in any base. Confining ourselves to 'decimal' numeric strings; the single digit numeric primes are prime in every base where they are a valid number.
- E.G.
The numeric string "2" is a prime in every base except base 2, where it is invalid.
The numeric string "3" is a prime in every base except base 2 and 3, where it is invalid.
"4" is not a prime in every base except bases 2, 3, and 4 where it is an invalid number (and hence not a prime there either.)
In general, even pan-base non-primes are much more prevalent than odd, though both are fairly common.
With the exception of "10", numeric strings that end in 0 are composite in every base where they are valid.
Numeric strings where the greatest common divisor of all of the digits is more than 1 are composite in every base.
If a "decimal" numeric string N is composite in every base up to base N, it is composite in every base.
The digit 1 is an odd-ball case as it is neither prime nor composite. It typically is not included, but due to the ambiguous wording, would not be wrong if it is.
- Task
- Find and display, here on this page, the first 40 pan-base non-prime "base 10" numeric strings.
- Find and display, here on this page, the first 20 odd pan-base non-prime "base 10" numeric strings.
- Find and display the count of pan-base non-prime "base 10" numeric strings up to at least the numeric string "1000".
- What percentage of them are odd / even?
- See also
ALGOL 68
BEGIN # pan-base non-primes - translated from the Wren sample #
PR read "primes.incl.a68" PR # include prime utilities #
INT limit = 2500;
# iterative Greatest Common Divisor routine, returns the gcd of m and n #
PROC gcd = ( INT m, n )INT:
BEGIN
INT a := ABS m, b := ABS n;
WHILE b /= 0 DO
INT new a = b;
b := a MOD b;
a := new a
OD;
a
END # gcd # ;
# table of digit-digit Greatest Common Divisors #
[ 0 : 9, 0 : 9 ]INT dd gcd;
FOR i FROM 0 TO 9 DO FOR j FROM 0 TO 9 DO dd gcd[ i, j ] := gcd( i, j ) OD OD;
# returns the gcd of the digits of n #
PROC gcd digits = ( INT n )INT:
BEGIN
STRING s = whole( n, 0 );
INT g := 0;
FOR c FROM LWB s TO UPB s DO
g := dd gcd[ g, ABS s[ c ] - ABS "0" ]
OD;
g
END # gcd digits # ;
# returns the number represented by s in base b #
# note s will only contain the digits 0 .. 9 #
PROC str to dec = ( STRING s, INT base )LONG INT:
BEGIN
LONG INT res := 0;
FOR c pos FROM LWB s TO UPB s DO
res *:= base +:= ( ABS s[ c pos ] - ABS "0" )
OD;
res
END # str to dec # ;
[ 1 : limit ]INT pbnp;
INT pbnp count := 0;
FOR n FROM 3 TO limit DO
IF n MOD 10 = 0 AND n > 10 THEN
pbnp[ pbnp count +:= 1 ] := n
ELIF n > 9 AND gcd digits( n ) > 1 THEN
pbnp[ pbnp count +:= 1 ] := n
ELSE
BOOL comp := TRUE;
STRING s = whole( n, 0 );
FOR base FROM 2 TO n WHILE comp := NOT is probably prime( str to dec( s, base ) ) DO SKIP OD;
IF comp THEN pbnp[ pbnp count +:= 1 ] := n FI
FI
OD;
print( ( "First 50 pan-base composites:", newline ) );
FOR i TO IF pbnp count < 50 THEN pbnp count ELSE 50 FI DO
print( ( " ", whole( pbnp[ i ], -3 ) ) );
IF i MOD 10 = 0 THEN print( ( newline ) ) FI
OD;
print( ( newline, "First 20 odd pan-base composites:", newline ) );
INT odd count := 0;
FOR i TO pbnp count DO
INT n = pbnp[ i ];
IF ODD n THEN
odd count +:= 1;
IF odd count <= 20 THEN
print( ( " ", whole( n, -3 ) ) );
IF odd count MOD 10 = 0 THEN print( ( newline ) ) FI
FI
FI
OD;
print( ( newline
, "Count of pan-base composites up to and including "
, whole( limit, 0 )
, ": "
, whole( pbnp count, 0 )
)
);
print( ( newline
, "Number odd = "
, whole( odd count, 0 )
, " or ", fixed( 100 * ( odd count / pbnp count ), -9, 6 )
, "%"
)
);
print( ( newline
, "Number even = "
, whole( pbnp count - odd count, 0 )
, " or ", fixed( 100 * ( ( pbnp count - odd count ) / pbnp count ), -9, 6 )
, "%"
)
)
END
- Output:
First 50 pan-base composites: 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100 110 112 114 116 118 120 121 130 132 134 136 First 20 odd pan-base composites: 9 33 39 55 63 69 77 93 99 121 143 165 169 187 231 253 273 275 297 299 Count of pan-base composites up to and including 2500: 953 Number odd = 161 or 16.894019% Number even = 792 or 83.105981%
J
Implementation:
pbnp=: {{ if. 10 > y do. -.1 p: y return. end.
digits=. 10 #.inv y
*/0=1 p: ((>./digits)+i.y) #."0 1 digits
}}"0
Task examples:
40{.1+I.pbnp 1+i.1e3 NB. first 40 pan based non primes
1 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100
20{.(#~ 2&|)1+I.pbnp 1+i.1e3 NB. first 20 odd pan based non primes
1 9 33 39 55 63 69 77 93 99 121 143 165 169 187 231 253 273 275 297
#1+I.pbnp 1+i.1e3 NB. number of pan based non primes up to 1000
378
#(#~ 2&|)1+I.pbnp 1+i.1e3 NB. number of odd pan based non primes up to 1000
64
100*(+/%#)2|1+I.pbnp 1+i.1e3 NB. percent odd pan based non primes up to 1000
16.9761
Julia
using Primes
ispanbasecomposite(n) = (d = digits(n); all(b -> !isprime(evalpoly(b, d)), maximum(d)+1:max(10, n)))
panbase2500 = filter(ispanbasecomposite, 2:2500)
oddpanbase2500 = filter(isodd, panbase2500)
ratio = length(oddpanbase2500) // length(panbase2500)
println("First 50 pan base non-primes:")
foreach(p -> print(lpad(p[2], 4), p[1] % 10 == 0 ? "\n" : ""), pairs(panbase2500[1:50]))
println("\nFirst 20 odd pan base non-primes:")
foreach(p -> print(lpad(p[2], 4), p[1] % 10 == 0 ? "\n" : ""), pairs(oddpanbase2500[1:20]))
println("\nCount of pan-base composites up to and including 2500: ", length(panbase2500))
println("Odd up to and including 2500: ", ratio, ", or ", Float16(ratio * 100), "%.")
println("Even up to and including 2500: ", 1 - ratio, ", or ", Float16((1.0 - ratio) * 100), "%.")
- Output:
First 50 pan base non-primes: 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100 110 112 114 116 118 120 121 130 132 134 136 First 20 odd pan base non-primes: 9 33 39 55 63 69 77 93 99 121 143 165 169 187 231 253 273 275 297 299 Count of pan-base composites up to and including 2500: 953 Odd up to and including 2500: 161//953, or 16.89%. Even up to and including 2500: 792//953, or 83.1%.
Pascal
Free Pascal
program PanBaseNonPrime;
// Check Pan-Base Non-Prime
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
// MAXLIMIT beyond 10000 gets really slow 5 digits, depends on isPrime
//10004 checked til base 10003 -> 10003⁴+3 = 1.0012e16, takes >1 s longer
//real 0m1,307s
// 9999 checked til base 9998 -> 8,99555E12 much smaller
//real 0m0,260s
type
tDgts = 0..31;// Int32 is faster than 0..9 -> word
tUsedDgts = set of tDgts;
tDecDigits = packed record
decdgts :array[0..20] of byte;
decmaxIdx :byte;
decmaxDgt :byte;
decUsedDgt :tUsedDgts;
end;
const
MAXLIMIT = 2500;
WithGCDNotOne : array[0..24] of tUsedDgts =
//all the same digits
([0],[2],[3],[4],[5],[6],[7],[8],[9],
//all even
[2,4],[2,6],[2,8],
[2,4,6],[2,4,8],[2,6,8],
[2,4,6,8],
[4,6],[4,8],
[4,6,8],[2,4,6,8],
[6,8],
//all divible 3
[3,6],[3,9],
[3,6,9],
[6,9]);
var
gblCnt,
gblOddCnt :NativeINt;
procedure OutDecDigits(var Dgts:tDecDigits);
var
idx : nativeInt;
begin
with Dgts do
begin
idx := decMaxIDx;
repeat
dec(idx);
write(decdgts[idx]);
until idx <= 0;
write(decmaxdgt:3);
writeln;
end;
end;
procedure CountOne(n:NativeInt);inline;
Begin
inc(gblCnt);
If odd(n) then
inc(gblOddCnt);
end;
procedure OutCountOne(n:NativeInt);
begin
CountOne(n);
write(n:5);
if gblCnt mod 10 = 0 then
writeln;
end;
function CheckGCD(var Dgts:tDecDigits):boolean;
var
idx: NativeInt;
UsedDgts:tUsedDgts;
begin
UsedDgts := Dgts.decUsedDgt;
For idx := Low(WithGCDNotOne) to High(WithGCDNotOne) do
if UsedDgts = WithGCDNotOne[idx] then
Exit(true);
Exit(false);
end;
procedure ConvToDecDgt(n : NativeUint;out Dgts:tDecDigits);//inline;
var
dgt,maxdgt,idx,q :NativeInt;
UsedDgts : tUsedDgts;
begin
UsedDgts := [];
maxdgt := 0;
idx := 0;
repeat
q := n div 10;
dgt := n-q*10;
Dgts.decdgts[idx]:= dgt;
include(UsedDgts,dgt);
IF maxdgt<dgt then
maxdgt := dgt;
inc(idx);
n := q;
until n = 0;
with Dgts do
Begin
decMaxIDx := idx;
decMaxdgt := maxDgt;
decUsedDgt := UsedDgts;
end;
end;
function ConvDgtToBase(var Dgts:tDecDigits;base:NativeInt):NativeUInt;
var
idx :NativeInt;
begin
result := 0;
if base<= Dgts.decMaxdgt then
EXIT;
with Dgts do
Begin
idx := decMaxIDx;
repeat
dec(idx);
result := result*base+decdgts[idx];
until idx <= 0;
end;
end;
function isPrime(n: NativeInt):boolean;
//simple trial division
var
j : nativeInt;
begin
if n in [2,3,5,7,11,13,17,19,23,29,31] then
EXIT(true);
if n<32 then
EXIT(false);
if not(odd(n)) then
EXIT(false);
if n mod 3 = 0 then
EXIT(false);
if n mod 5 = 0 then
EXIT(false);
j := 7;
while j*j<=n do
begin
if n mod j = 0 then
EXIT(false);
inc(j,4);
if n mod j = 0 then
EXIT(false);
inc(j,2);
end;
EXIT(true);
end;
function CheckPanBaseNonPrime(n: NativeUint):boolean;
var
myDecDgts:tDecDigits;
b,num : NativeInt;
Begin
result := true;
ConvToDecDgt(n,myDecDgts);
if (n>10) then
Begin
if (myDecDgts.decdgts[0] = 0) then
Exit;
if CheckGCD(myDecDgts) then
Exit;
end;
b := myDecDgts.decmaxdgt+1;
if b >= n then
Begin
if isPrime(n) then
Exit(false);
end
else
begin
while b < n do
begin
num := ConvDgtToBase(myDecDgts,b);
if isPrime(num) then
EXIT(false);
inc(b);
end;
end;
end;
var
i : NativeInt;
BEGIN
writeln('First 50 pan-base non-prime numbers ');
gblCnt := 0;
gblOddCnt := 0;
For i := 3 to MAXLIMIT do
Begin
if CheckPanBaseNonPrime(i) then
OutCountOne(i);
if gblCnt = 50 then
break;
end;
writeln;
writeln('First 20 pan-base non-prime odd numbers ');
gblCnt := 0;
gblOddCnt := 0;
For i := 3 to MAXLIMIT do
Begin
if ODD(i) then
Begin
if CheckPanBaseNonPrime(i) then
OutCountOne(i);
if gblOddCnt = 20 then
break;
end;
end;
writeln;
gblCnt := 0;
gblOddCnt := 0;
For i := 3 to MAXLIMIT do
if CheckPanBaseNonPrime(i) then
CountOne(i);
writeln('Count of pan-base composites up to and including ',MAXLIMIT,' : ',gblCnt);
writeln('odd up to and including ',MAXLIMIT,' = ',gblOddCnt:4,' equals ',gblOddCnt/gblCnt*100:10:6,'%');
writeln('even up to and including ',MAXLIMIT,' = ',gblCnt-gblOddCnt:4,' equals ',(gblCnt-gblOddCnt)/gblCnt*100:10:6,'%');
END.
- Output:
First 50 pan-base non-prime numbers 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100 110 112 114 116 118 120 121 130 132 134 136 First 20 pan-base non-prime odd numbers 9 33 39 55 63 69 77 93 99 121 143 165 169 187 231 253 273 275 297 299 Count of pan-base composites up to and including 2500 : 953 odd up to and including 2500 = 161 equals 16.894019% even up to and including 2500 = 792 equals 83.105981%
Phix
with javascript_semantics constant lim = 2500 sequence pbnp = {} for n=3 to lim do sequence digits = sq_sub(sprintf("%d",n),'0') if (remainder(n,10)=0 and n>10) or (n>9 and gcd(digits)>1) then pbnp &= n else bool composite = true for base=2 to n do atom d = 0 for c in digits do d = d*base + c end for if is_prime(d) then composite = false exit end if end for if composite then pbnp &= n end if end if end for sequence odds = filter(pbnp,odd) integer tc = length(pbnp), oc = length(odds), ec = tc-oc string f50 = join_by(pbnp[1..50],1,10," ",fmt:="%3d"), o20 = join_by(odds[1..20],1,10," ",fmt:="%3d") printf(1,"First 50 pan-base composites:\n%s\n",f50) printf(1,"First 20 odd pan-base composites:\n%s\n",o20) printf(1,"Count of pan-base composites up to and including %d: %d\n",{lim,tc}) printf(1,"Number odd = %3d or %9.6f%%\n", {oc,oc/tc*100}) printf(1,"Number even = %3d or %9.6f%%\n", {ec,ec/tc*100})
Output same as Wren
Raku
use Base::Any;
use List::Divvy;
my @np = 4,6,8,9, |lazy (11..*).hyper.grep( -> $n { ($n.substr(*-1) eq '0') || (1 < [gcd] $n.comb».Int) || none (2..$n).map: { try "$n".&from-base($_).is-prime } } );
put "First 50 pan-base composites:\n" ~ @np[^50].batch(10)».fmt("%3s").join: "\n";
put "\nFirst 20 odd pan-base composites:\n" ~ @np.grep(* % 2)[^20].batch(10)».fmt("%3s").join: "\n";
my $threshold = 2500;
put "\nCount of pan-base composites up to and including $threshold: " ~ +@np.&upto($threshold);
put "Percent odd up to and including $threshold: " ~ +@np.&upto($threshold).grep(* % 2) / +@np.&upto($threshold) × 100;
put "Percent even up to and including $threshold: " ~ +@np.&upto($threshold).grep(* %% 2) / +@np.&upto($threshold) × 100;
- Output:
First 50 pan-base composites: 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100 110 112 114 116 118 120 121 130 132 134 136 First 20 odd pan-base composites: 9 33 39 55 63 69 77 93 99 121 143 165 169 187 231 253 273 275 297 299 Count of pan-base composites up to and including 2500: 953 Percent odd up to and including 2500: 16.894019 Percent even up to and including 2500: 83.105981
Wren
import "./math" for Int
import "./fmt" for Fmt
var strToDec = Fn.new { |s, b|
var res = 0
for (c in s) {
var d = Num.fromString(c)
res = res * b + d
}
return res
}
var limit = 2500
var pbnp = []
for (n in 3..limit) {
if (n % 10 == 0 && n > 10) {
pbnp.add(n)
} else if (n > 9 && Int.gcd(Int.digits(n)) > 1) {
pbnp.add(n)
} else {
var comp = true
for (b in 2...n) {
var d = strToDec.call(n.toString, b)
if (Int.isPrime(d)) {
comp = false
break
}
}
if (comp) pbnp.add(n)
}
}
System.print("First 50 pan-base composites:")
Fmt.tprint("$3d", pbnp[0..49], 10)
System.print("\nFirst 20 odd pan-base composites:")
var odd = pbnp.where { |n| n % 2 == 1 }.toList
Fmt.tprint("$3d", odd[0..19], 10)
var tc
System.print("\nCount of pan-base composites up to and including %(limit): %(tc = pbnp.count)")
var c
Fmt.print("Number odd = $3d or $9.6f\%", c = odd.count, c/tc * 100)
Fmt.print("Number even = $3d or $9.6f\%", c = tc - c, c/tc * 100)
- Output:
First 50 pan-base composites: 4 6 8 9 20 22 24 26 28 30 33 36 39 40 42 44 46 48 50 55 60 62 63 64 66 68 69 70 77 80 82 84 86 88 90 93 96 99 100 110 112 114 116 118 120 121 130 132 134 136 First 20 odd pan-base composites: 9 33 39 55 63 69 77 93 99 121 143 165 169 187 231 253 273 275 297 299 Count of pan-base composites up to and including 2500: 953 Number odd = 161 or 16.894019% Number even = 792 or 83.105981%