Pan base non-primes: Difference between revisions
→{{header|PARI/GP}}: fix jump anchor problem
(Added C++ solution) |
(→{{header|PARI/GP}}: fix jump anchor problem) |
||
| (10 intermediate revisions by 7 users not shown) | |||
Line 1:
{{
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.)
Line 167:
Number odd = 161 or 16.894019%
Number even = 792 or 83.105981%
</pre>
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
bool is_prime(uint64_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
if (n % 5 == 0)
return n == 5;
static const uint64_t wheel[] = {4, 2, 4, 2, 4, 6, 2, 6};
for (uint64_t p = 7;;) {
for (int i = 0; i < 8; ++i) {
if (p * p > n)
return true;
if (n % p == 0)
return false;
p += wheel[i];
}
}
}
// Compute the digits of n in base 10, least significant digit first.
int digits(uint64_t n, uint8_t* d, int size) {
int count = 0;
for (; n > 0 && size > 0; n /= 10, --size, ++count)
*d++ = n % 10;
return count;
}
// Convert digits in the given base to a number (least significant digit first).
uint64_t from_digits(uint8_t* a, int count, uint64_t base) {
uint64_t n = 0;
while (count-- > 0)
n = n * base + a[count];
return n;
}
#define MAX_DIGITS 20
bool is_pan_base_non_prime(uint64_t n) {
if (n < 10)
return !is_prime(n);
if (n > 10 && n % 10 == 0)
return true;
uint8_t d[MAX_DIGITS];
int count = digits(n, d, MAX_DIGITS);
uint8_t max_digit = 0;
for (int i = 0; i < count; ++i) {
if (max_digit < d[i])
max_digit = d[i];
}
for (uint64_t base = max_digit + 1; base <= n; ++base) {
if (is_prime(from_digits(d, count, base)))
return false;
}
return true;
}
int main() {
printf("First 50 prime pan-base composites:\n");
int count = 0;
for (uint64_t n = 2; count < 50; ++n) {
if (is_pan_base_non_prime(n)) {
++count;
printf("%3llu%c", n, count % 10 == 0 ? '\n' : ' ');
}
}
printf("\nFirst 20 odd prime pan-base composites:\n");
count = 0;
for (uint64_t n = 3; count < 20; n += 2) {
if (is_pan_base_non_prime(n)) {
++count;
printf("%3llu%c", n, count % 10 == 0 ? '\n' : ' ');
}
}
const uint64_t limit = 10000;
int odd = 0;
count = 0;
for (uint64_t n = 2; n <= limit; ++n) {
if (is_pan_base_non_prime(n)) {
++count;
if (n % 2 == 1)
++odd;
}
}
printf("\nCount of pan-base composites up to and including %llu: %d\n",
limit, count);
double percent = 100.0 * odd / count;
printf("Percent odd up to and including %llu: %f\n", limit, percent);
printf("Percent even up to and including %llu: %f\n", limit,
100.0 - percent);
return 0;
}</syntaxhighlight>
{{out}}
<pre>
First 50 prime 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 prime 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 10000: 3849
Percent odd up to and including 10000: 18.030657
Percent even up to and including 10000: 81.969343
</pre>
Line 292 ⟶ 413:
Percent even up to and including 10000: 81.969343
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
if num mod 2 = 0
if num = 2
return 1
.
return 0
.
if num mod 3 = 0
if num = 3
return 1
.
return 0
.
i = 5
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
if num mod i = 0
return 0
.
i += 4
.
return 1
.
proc digits n . d[] .
while n > 0
d[] &= n mod 10
n = n div 10
.
.
proc fromdigits b . d[] n .
n = 0
for i = len d[] downto 1
n = n * b + d[i]
.
.
func panbasenpr n .
if n < 10
return 1 - isprim n
.
if n > 10 and n mod 10 = 0
return 1
.
digits n d[]
for i to len d[]
if maxdig < d[i]
maxdig = d[i]
.
.
for base = maxdig + 1 to n
fromdigits base d[] n
if isprim n = 1
return 0
.
.
return 1
.
print "First 50 prime pan-base composites:"
n = 2
repeat
if panbasenpr n = 1
cnt += 1
write n & " "
.
until cnt = 50
n += 1
.
cnt = 0
print "\n\nFirst 20 odd prime pan-base composites:"
n = 3
repeat
if panbasenpr n = 1
cnt += 1
write n & " "
.
until cnt = 20
n += 2
.
limit = 10000
cnt = 0
for n = 2 to limit
if panbasenpr n = 1
cnt += 1
if n mod 2 = 1
odd += 1
.
.
.
print "\nCount of pan-base composites up to and including " & limit & ": " & cnt
p = 100 * odd / cnt
print "Percent odd up to and including " & limit & ": " & p
print "Percent even up to and including " & limit & ": " & 100 - p
</syntaxhighlight>
=={{header|J}}==
Line 308 ⟶ 527:
100*(+/%#)2|1+I.pbnp 1+i.1e3 NB. percent odd pan based non primes up to 1000
16.9761</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">public class PanBaseNonPrimes {
public static void main(String[] args) {
System.out.printf("First 50 prime pan-base composites:\n");
int count = 0;
for (long n = 2; count < 50; ++n) {
if (isPanBaseNonPrime(n)) {
++count;
System.out.printf("%3d%c", n, count % 10 == 0 ? '\n' : ' ');
}
}
System.out.printf("\nFirst 20 odd prime pan-base composites:\n");
count = 0;
for (long n = 3; count < 20; n += 2) {
if (isPanBaseNonPrime(n)) {
++count;
System.out.printf("%3d%c", n, count % 10 == 0 ? '\n' : ' ');
}
}
final long limit = 10000;
count = 0;
int odd = 0;
for (long n = 2; n <= limit; ++n) {
if (isPanBaseNonPrime(n)) {
++count;
if (n % 2 == 1)
++odd;
}
}
System.out.printf("\nCount of pan-base composites up to and including %d: %d\n",
limit, count);
double percent = 100.0 * odd / count;
System.out.printf("Percent odd up to and including %d: %f\n",
limit, percent);
System.out.printf("Percent even up to and including %d: %f\n",
limit, 100.0 - percent);
}
private static boolean isPanBaseNonPrime(long n) {
if (n < 10)
return !isPrime(n);
if (n > 10 && n % 10 == 0)
return true;
byte[] d = new byte[20];
int count = digits(n, d);
byte max_digit = 0;
for (int i = 0; i < count; ++i) {
if (max_digit < d[i])
max_digit = d[i];
}
for (long base = max_digit + 1; base <= n; ++base) {
if (isPrime(fromDigits(d, count, base)))
return false;
}
return true;
}
private static final long[] WHEEL = {4, 2, 4, 2, 4, 6, 2, 6};
private static boolean isPrime(long n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
if (n % 5 == 0)
return n == 5;
for (long p = 7;;) {
for (int i = 0; i < 8; ++i) {
if (p * p > n)
return true;
if (n % p == 0)
return false;
p += WHEEL[i];
}
}
}
// Compute the digits of n in base 10, least significant digit first.
private static int digits(long n, byte[] d) {
int count = 0;
for (; n > 0 && count < d.length; n /= 10, ++count)
d[count] = (byte)(n % 10);
return count;
}
// Convert digits in the given base to a number (least significant digit first).
private static long fromDigits(byte[] a, int count, long base) {
long n = 0;
while (count-- > 0)
n = n * base + a[count];
return n;
}
}</syntaxhighlight>
{{out}}
<pre>
First 50 prime 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 prime 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 10000: 3849
Percent odd up to and including 10000: 18.030657
Percent even up to and including 10000: 81.969343
</pre>
=={{header|Julia}}==
Line 344 ⟶ 680:
Odd up to and including 2500: 161//953, or 16.89%.
Even up to and including 2500: 792//953, or 83.1%.
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Julia}}
<syntaxhighlight lang="Mathematica">(* Define the function to check if a number is a pan base composite *)
IsPanBaseComposite[n_] := Module[
{d = IntegerDigits[n], bases, compositeInAllBases},
bases = Range[Max[d] + 1, Max[10, n]];
compositeInAllBases = Not /@ PrimeQ[FromDigits[d, #] & /@ bases];
AllTrue[compositeInAllBases, Identity]
]
(* Generate the list of all pan base composites up to 2500 *)
panBase2500 = Select[Range[2, 2500], IsPanBaseComposite]
(* Filter out the odd numbers from the pan base composites *)
oddPanBase2500 = Select[panBase2500, OddQ]
(* Calculate the ratio of odd pan base composites to all pan base composites *)
ratio = Length[oddPanBase2500] / Length[panBase2500]
(* Print the first 50 pan base non-primes *)
Print["First 50 pan base non-primes:"]
Print[StringJoin[Riffle[ToString /@ Take[panBase2500, 50], ", "]]]
(* Print the first 20 odd pan base non-primes *)
Print["\nFirst 20 odd pan base non-primes:"]
Print[StringJoin[Riffle[ToString /@ Take[oddPanBase2500, 20], ", "]]]
(* Print the count of pan-base composites up to and including 2500 *)
Print["\nCount of pan-base composites up to and including 2500: ", Length[panBase2500]]
(* Print the ratios *)
Print["Odd up to and including 2500: ", Rationalize[ratio], ", or ", N[ratio * 100, 4], "%."]
Print["Even up to and including 2500: ", Rationalize[1 - ratio], ", or ", N[(1 - ratio) * 100, 4], "%."]</syntaxhighlight>
{{out}}
<pre>
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.894018887722980063`4.%.
Even up to and including 2500: 792/953, or 83.105981112277019937`4.%.
</pre>
=={{header|Nim}}==
{{trans|C}}
<syntaxhighlight lang="Nim">import std/strformat
func isPrime(n: int64): bool =
const Wheel = [4, 2, 4, 2, 4, 6, 2, 6]
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
if n mod 5 == 0: return n == 5
var p = 7
while true:
for w in Wheel:
if p * p > n: return true
if n mod p == 0: return false
inc p, w
func digits(n: int64): seq[byte] =
## Compute the digits of n in base 10, least significant digit first.
var n = n
while n != 0:
result.add byte(n mod 10)
n = n div 10
func fromDigits(a: seq[byte]; base: Positive): int64 =
## Convert digits in the given base to a number (least significant digit first).
for i in countdown(a.high, 0):
result = result * base + a[i].int
func isPanBaseNonPrime(n: int64): bool =
if n < 10: return not n.isPrime()
if n > 10 and n mod 10 == 0: return true
let d = n.digits
let maxDigit = max(d).int
for base in (maxDigit + 1)..n:
if d.fromDigits(base).isPrime():
return false
result = true
echo "First 50 prime pan-base composites:"
var count = 0;
var n = 2
while count < 50:
if n.isPanBaseNonPrime():
inc count
stdout.write &"{n:3}", if count mod 10 == 0: '\n' else: ' '
inc n
echo "\nFirst 20 odd prime pan-base composites:"
count = 0
n = 3
while count < 20:
if n.isPanBaseNonPrime():
inc count
stdout.write &"{n:3}", if count mod 10 == 0: '\n' else: ' '
inc n, 2
const Limit = 10_000
var odd = 0
count = 0
for n in 2..Limit:
if n.isPanBaseNonPrime():
inc count
if (n and 1) == 1:
inc odd
echo &"\nCount of pan-base composites up to and including {Limit}: {count}"
let percent = 100 * odd / count
echo &"Percent odd up to and including {Limit}: {percent:.6f}"
echo &"Percent even up to and including {Limit}: {100 - percent:.6f}"
</syntaxhighlight>
{{out}}
<pre>First 50 prime 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 prime 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 10000: 3849
Percent odd up to and including 10000: 18.030657
Percent even up to and including 10000: 81.969343
</pre>
=={{header|PARI/GP}}==
{{trans|Mathematica/Wolfram_Language}}
<syntaxhighlight lang="parigp">
/* Define the function to check if a number is not prime in all bases greater than its maximum digit */
is_pan_base_composite(n) = {
my(d = digits(n), base, isComp);
for (base = vecmax(d)+1, max(n, 10),
isComp = !isprime(fromdigits(d, base));
if (!isComp, return(0)); /* If number is prime in any base, return false */
);
return(1); /* Number is composite in all bases */
}
/* Generate the list of all pan base composites up to 2500 */
pan_base_2500 = select(is_pan_base_composite, [2..2500]);
/* Define a function to check if a number is odd */
is_odd(n) = n % 2 == 1;
/* Filter out the odd numbers from the pan base composites */
odd_pan_base_2500 = select(is_odd, pan_base_2500);
/* Calculate the ratio of odd pan base composites to all pan base composites */
ratio = #odd_pan_base_2500 / #pan_base_2500;
/* Print the first 50 pan base non-primes */
print("First 50 pan base non-primes:");
print(concat("", vector(min(#pan_base_2500, 50), i, Str(pan_base_2500[i]))));
/* Print the first 20 odd pan base non-primes */
print("\nFirst 20 odd pan base non-primes:");
print(concat("", vector(min(#odd_pan_base_2500, 20), i, Str(odd_pan_base_2500[i]))));
/* Print the count of pan-base composites up to and including 2500 */
print("\nCount of pan-base composites up to and including 2500: ", #pan_base_2500);
/* Print the ratios */
default(realprecision, 4)
print("Odd up to and including 2500: ", ratio, ", or ", ratio * 100.0, "%.");
print("Even up to and including 2500: ", 1 - ratio, ", or ", (1 - ratio) * 100.0, "%.");
</syntaxhighlight>
{{out}}
<pre>
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.11%.
</pre>
Line 700 ⟶ 1,226:
Percent odd up to and including 2500: 16.894019
Percent even up to and including 2500: 83.105981</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
def int_from_digits(ar, base=10)
# expects array from digits method, which takes a base as argument and gives least significant digit first.
raise ArgumentError, "#{ar.max} not valid in base #{base}. " if ar.max > base-1
ar.each_with_index.sum {|d, i| d*base**i }
end
limit = 2500
a121719 = (2..limit).lazy.select do |n|
next false if (n < 10 && n.prime?)
digits = n.digits
from = digits.max + 1
(from..n).none?{|base| int_from_digits(digits, base).prime? }
end
n = 50
puts "First #{n} pan-base composites:"
a121719.take(n).each_slice(10){|s| puts "%4s"*s.size % s}
n = 20
puts "\nFirst #{n} odd pan-base composites:"
a121719.select(&:odd?).take(n).each_slice(10){|s| puts "%4s"*s.size % s }
tally = a121719.map(&:odd?).tally
total = tally.values.sum
puts "\nCount of pan-base composites up to and including #{limit}: #{total}"
puts "Number of odds is #{tally[true ]}, proportion #{tally[true ].fdiv(total) }%"
puts "Number of evens is #{tally[false]}, proportion #{tally[false].fdiv(total) }%"</syntaxhighlight>
{{out}}
<pre>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 of odds is 161, proportion 0.1689401888772298%
Number of evens is 792, proportion 0.8310598111227702%
</pre>
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||