Iccanobif primes
Iccanobif primes are prime numbers that, when reversed, are a Fibonacci number.
Iccanobif primes 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.
- Task
- Find and display the first 10 iccanobif primes.
- Stretch
- Find and display the digit count of the next 15 iccanobif primes.
- See also
ALGOL 68
BEGIN # show the first 10 prime Iccanobif (reversed Fibonacci) numbers #
# returns n with the digits reversed #
OP REVERSE = ( INT n )INT:
BEGIN
INT reverse := 0;
INT v := ABS n;
WHILE v > 0 DO
reverse *:= 10 +:= v MOD 10;
v OVERAB 10
OD;
reverse * SIGN n
END # REVERSE # ;
# returns TRUE if n is prime, FALSE otherwise - uses trial division #
PROC is prime = ( LONG INT n )BOOL:
IF n < 3 THEN n = 2
ELIF n MOD 3 = 0 THEN n = 3
ELIF NOT ODD n THEN FALSE
ELSE
BOOL is a prime := TRUE;
INT f := 5;
INT f2 := 25;
INT to next := 24;
WHILE f2 <= n AND is a prime DO
is a prime := n MOD f /= 0;
f +:= 2;
f2 +:= to next;
to next +:= 8
OD;
is a prime
FI # is prime # ;
# task #
INT p count := 0;
INT prev := 0;
INT curr := 1;
WHILE p count < 10 DO
INT next = prev + curr;
prev := curr;
curr := next;
INT rev := REVERSE curr;
IF is prime( rev ) THEN
# have a prime iccanobif number #
p count +:= 1;
print( ( " ", whole( rev, 0 ) ) )
FI
OD
END- Output:
2 3 5 31 43 773 7951 64901 52057 393121
Arturo
summarize: function [n :string][
;; description: « returns a summary of a numeric string
s: size n
if s > 20 -> n: ((take n 10)++"...")++drop n s-10
n ++ ~" (|s| digits)"
]
[a b count]: [0 1 0]
print "First 27 Iccanobif primes:"
while -> count < 27 [
if prime? to :integer r: <= reverse ~"|a|" [
print [pad ~"|count+1|" 2 "->" summarize r]
inc 'count
]
[a b]: @[b a+b]
]
- Output:
First 27 Iccanobif primes: 1 -> 2 (1 digits) 2 -> 3 (1 digits) 3 -> 5 (1 digits) 4 -> 31 (2 digits) 5 -> 43 (2 digits) 6 -> 773 (3 digits) 7 -> 7951 (4 digits) 8 -> 64901 (5 digits) 9 -> 52057 (5 digits) 10 -> 393121 (6 digits) 11 -> 56577108676171 (14 digits) 12 -> 9406476074...3258103531 (21 digits) 13 -> 5237879497...9575442761 (37 digits) 14 -> 9026258083...2307801963 (40 digits) 15 -> 1990033567...3266446403 (80 digits) 16 -> 7784113736...3685331923 (104 digits) 17 -> 3772258590...2830756131 (137 digits) 18 -> 7573619389...4714305761 (330 digits) 19 -> 1789033684...5235035913 (406 digits) 20 -> 9232716310...6047302507 (409 digits) 21 -> 5042015781...7362214481 (503 digits) 22 -> 3051101247...1330018201 (888 digits) 23 -> 4681854704...4645856321 (1020 digits) 24 -> 8710134785...8865227391 (1122 digits) 25 -> 1745165602...1843652461 (1911 digits) 26 -> 4898934056...4215909399 (1947 digits) 27 -> 1274692768...7994940101 (2283 digits)
BASIC
BASIC256
#include "isprime.kbs"
cnt = 0 : prev = 0 : curr = 1
print "First 10 iccanobiF primes:"
while cnt < 10
sgte = prev + curr
prev = curr
curr = sgte
rev = reverseNumber(curr)
if isPrime(rev) then
# have a prime iccanobif number
cnt += 1
print rev; " ";
end if
end while
end
function reverseNumber(num)
if num < 10 then return num
reverse = 0
while num > 0
reverse = 10 * reverse + num mod 10
num = int(num / 10)
end while
return reverse
end function
FreeBASIC
#include "isprime.bas"
' returns num with the digits reversed
Function reverseNumber(num As Uinteger) As Uinteger
If num < 10 Then Return num
Dim As Integer reverse = 0
While num > 0
reverse = 10 * reverse + (num Mod 10)
num \= 10
Wend
Return reverse
End Function
Dim As Byte cnt = 0
Dim As Uinteger prev = 0, curr = 1
Dim As Uinteger sgte, rev
Print "First 11 iccanobiF primes:"
While cnt < 11
sgte = prev + curr
prev = curr
curr = sgte
rev = reverseNumber(curr)
If isPrime(rev) Then
' have a prime iccanobif number
cnt += 1
Print rev; " ";
End If
Wend
Sleep- Output:
First 11 iccanobiF primes: 2 3 5 31 43 773 7951 64901 52057 393121 56577108676171
Gambas
Public Sub Main()
Dim cnt As Short = 0, prev As Long = 0, curr As Long = 1
Dim sgte As Long, rev As Long
Print "First 11 iccanobiF primes:"
While cnt < 11
sgte = prev + curr
prev = curr
curr = sgte
rev = reverseNumber(curr)
If isPrime(rev) Then
' have a prime iccanobif number
cnt += 1
Print rev; " ";
End If
Wend
Print
End
Function reverseNumber(num As Long) As Long
If num < 10 Then Return num
Dim reverse As Long = 0
While num > 0
reverse = 10 * reverse + (num Mod 10)
num \= 10
Wend
Return reverse
End Function
Sub isPrime(ValorEval As Long) As Boolean
If ValorEval < 2 Then Return False
If ValorEval Mod 2 = 0 Then Return ValorEval = 2
If ValorEval Mod 3 = 0 Then Return ValorEval = 3
Dim d As Long = 5
While d * d <= ValorEval
If ValorEval Mod d = 0 Then Return False Else d += 2
Wend
Return True
End Function
- Output:
Same as FreeBASIC entry.
Yabasic
//import isprime
cnt = 0 : prev = 0 : curr = 1
print "First 10 iccanobiF primes:"
while cnt < 10
sgte = prev + curr
prev = curr
curr = sgte
rev = reverseNumber(curr)
if isPrime(rev) then
// have a prime iccanobif number
cnt = cnt + 1
print rev, " ";
fi
wend
print
end
sub reverseNumber(num)
local revers
if num < 10 return num
revers = 0
while num > 0
revers = 10 * revers + mod(num, 10)
num = int(num / 10)
wend
return revers
end subC
There's a big jump in digit count between the 29th and 30th numbers and consequently the latter is very slow indeed to emerge.
#include <stdio.h>
#include <string.h>
#include <gmp.h>
char *reverse(char *s) {
int i, j, len = strlen(s);
char t;
for (i = 0, j = len - 1; i < j; ++i, --j) {
t = s[i];
s[i] = s[j];
s[j] = t;
}
return s;
}
int main() {
int count = 0;
size_t len;
char *s, a[44];
mpz_t fib, p, prev, curr;
mpz_init(fib);
mpz_init(p);
mpz_init_set_ui(prev, 0);
mpz_init_set_ui(curr, 1);
printf("First 30 Iccanobif primes:\n");
while (count < 30) {
mpz_add(fib, curr, prev);
s = mpz_get_str(NULL, 10, fib);
mpz_set_str(p, reverse(s), 10);
if (mpz_probab_prime_p(p, 15) > 0) {
++count;
s = mpz_get_str(NULL, 10, p);
len = strlen(s);
if (len > 40) {
strncpy(a, s, 20);
strcpy(a + 20, "...");
strncpy(a + 23, s + len - 20, 21);
}
printf("%2d: %s (%ld digits)\n", count, len <= 40 ? s : a, len);
}
mpz_set(prev, curr);
mpz_set(curr, fib);
}
mpz_clear(fib);
mpz_clear(p);
mpz_clear(prev);
mpz_clear(curr);
return 0;
}
- Output:
Same as Wren example.
jq
Works with jq and gojq, the C and Go implementations of jq
The following program will also work using jaq, the Rust implementation of jq, provided the adjustments described in the Addendum are made.
gojq supports infinite-precision integer arithmetic, but the `sqrt` algorithm presented here is insufficient for computing the 12th Iccanobif prime in a reasonable time.
def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else
($n | sqrt) as $rt
| 23
| until( . > $rt or ($n % . == 0); .+2)
| . > $rt
end;
# Output: an indefinitely long stream of fibonacci numbers subject to
# integer arithmetic limitations if any
def fib: [0,1]|while(1;[last,add])[1];
def reverseNumber: tostring | explode | reverse | implode | tonumber;
"First 11 Iccanobif primes:",
limit(11; fib | tostring | reverseNumber | select(is_prime))- Output:
First 11 Iccanobif primes: 2 3 5 31 43 773 7951 64901 52057 393121 56577108676171
Addendum: jaq version
jaq does not have indefinite-precision integer arithmetic, so here we'll just briefly summarize the tweaks needed:
(1) Use `isqrt` as defined at Isqrt_(integer_square_root)_of_X#jq but with the addition of `floor` at the end of the def of `idivide`.
(2) Replace reverseNumber so that leading 0s do not appear in the reversed string:
# Input: an array of codepoints
# 48 is the codepoint of "0"
def rmLeadingZeros:
if .[0] == 48 then .[1:] | rmLeadingZeros else . end;
def reverseNumber: tostring | explode | reverse | rmLeadingZeros | implode | tonumber;Julia
using Primes
""" Print the series of iccanobif prime numbers up to wanted """
function iccanobifs(wanted)
digbuf = zeros(Int, 11000)
fib, prev, prevprev, fcount = big"0", big"1", big"0", 0
println("First $wanted Iccanobif primes:")
while fcount < wanted
fib = prev + prevprev
prevprev = prev
prev = fib
digits!(digbuf, fib)
candidate = evalpoly(big"10", reverse(digbuf[begin:findlast(!iszero, digbuf)]))
if isprime(candidate)
fcount += 1
dlen = ndigits(candidate)
if dlen < 90
println(candidate, " ($dlen digit$(dlen == 1 ? "" : "s"))")
else
s = string(candidate)
println(s[1:30], " ... ", s[end-29:end], " ($dlen digits)")
end
end
end
end
iccanobifs(30)
- Output:
First 30 Iccanobif primes: 2 (1 digit) 3 (1 digit) 5 (1 digit) 31 (2 digits) 43 (2 digits) 773 (3 digits) 7951 (4 digits) 64901 (5 digits) 52057 (5 digits) 393121 (6 digits) 56577108676171 (14 digits) 940647607443258103531 (21 digits) 5237879497657222310489731409575442761 (37 digits) 9026258083384996860449366072142307801963 (40 digits) 19900335674812302969315720344396951060628175943800862267761734431012073266446403 (80 digits) 778411373629674799853537498387 ... 906414225852312097783685331923 (104 digits) 377225859015676041888905465423 ... 942640418929174997072830756131 (137 digits) 757361938948761315956093082097 ... 105343825250767238644714305761 (330 digits) 178903368473328376208382371633 ... 139766460613175300695235035913 (406 digits) 923271631017291153059188123189 ... 439342926827061468856047302507 (409 digits) 504201578106980562530763299184 ... 034364678167335124247362214481 (503 digits) 305110124747393800923565587415 ... 827995099969296158361330018201 (888 digits) 468185470426936945550027667953 ... 673037342708664543144645856321 (1020 digits) 871013478530378198843208828928 ... 472170748420128396998865227391 (1122 digits) 174516560225437653361964336594 ... 630820185220100243761843652461 (1911 digits) 489893405662883994748316933771 ... 474664296802930339234215909399 (1947 digits) 127469276849582096547381559312 ... 119580690153436989647994940101 (2283 digits) 357468265826587510126602192036 ... 869346589325010735912438195633 (3727 digits) 879871752812976577066489068488 ... 466056251048748727893681871587 (4270 digits) 818073763671137983636050093057 ... 882798314213687506007959668569 (10527 digits)
Perl
use strict;
use warnings;
use ntheory qw<is_prime lucasu>;
sub abbr ($d,$w) { my $l = length $d; $l < $w+1 ? $d : substr($d,0,$w/2) . '..' . substr($d,-$w/2) . " ($l digits)" }
my($n,$cnt) = (0,0);
do {
my $f = lucasu(1, -1, $n++);
my $p = join '', reverse split '', $f;
printf "%-2d: %s\n", ++$cnt, abbr($p,50) if is_prime $p;
} until $cnt == 25;
- Output:
1 : 2 2 : 3 3 : 5 4 : 31 5 : 43 6 : 773 7 : 7951 8 : 64901 9 : 52057 10: 393121 11: 56577108676171 12: 940647607443258103531 13: 5237879497657222310489731409575442761 14: 9026258083384996860449366072142307801963 15: 1990033567481230296931572..7761734431012073266446403 (80 digits) 16: 7784113736296747998535374..4225852312097783685331923 (104 digits) 17: 3772258590156760418889054..0418929174997072830756131 (137 digits) 18: 7573619389487613159560930..3825250767238644714305761 (330 digits) 19: 1789033684733283762083823..6460613175300695235035913 (406 digits) 20: 9232716310172911530591881..2926827061468856047302507 (409 digits) 21: 5042015781069805625307632..4678167335124247362214481 (503 digits) 22: 3051101247473938009235655..5099969296158361330018201 (888 digits) 23: 4681854704269369455500276..7342708664543144645856321 (1020 digits) 24: 8710134785303781988432088..0748420128396998865227391 (1122 digits) 25: 1745165602254376533619643..0185220100243761843652461 (1911 digits)
Python
""" rosettacode.org/wiki/Iccanobif_primes """
from sympy import isprime
def iccanobifs(wanted):
""" Print the series of iccanobif prime numbers up to wanted """
fib, prev, prevprev, fcount = 0, 1, 0, 0
print('First 30 Iccanobif primes:')
while fcount < wanted:
fib = prev + prevprev
prevprev = prev
prev = fib
dig = [int(c) for c in str(fib)]
candidate = sum(n * 10**i for i, n in enumerate(dig))
if isprime(candidate):
fcount += 1
dlen = len(str(candidate))
if dlen < 90:
print(candidate, f"({dlen} digit{'' if dlen == 1 else 's'})")
else:
s = str(candidate)
print(s[:30], "...", s[-29:], f'({dlen} digits)')
iccanobifs(30)
- Output:
First 30 Iccanobif primes: 2 (1 digit) 3 (1 digit) 5 (1 digit) 31 (2 digits) 43 (2 digits) 773 (3 digits) 7951 (4 digits) 64901 (5 digits) 52057 (5 digits) 393121 (6 digits) 56577108676171 (14 digits) 940647607443258103531 (21 digits) 5237879497657222310489731409575442761 (37 digits) 9026258083384996860449366072142307801963 (40 digits) 19900335674812302969315720344396951060628175943800862267761734431012073266446403 (80 digits) 778411373629674799853537498387 ... 06414225852312097783685331923 (104 digits) 377225859015676041888905465423 ... 42640418929174997072830756131 (137 digits) 757361938948761315956093082097 ... 05343825250767238644714305761 (330 digits) 178903368473328376208382371633 ... 39766460613175300695235035913 (406 digits) 923271631017291153059188123189 ... 39342926827061468856047302507 (409 digits) 504201578106980562530763299184 ... 34364678167335124247362214481 (503 digits) 305110124747393800923565587415 ... 27995099969296158361330018201 (888 digits) 468185470426936945550027667953 ... 73037342708664543144645856321 (1020 digits) 871013478530378198843208828928 ... 72170748420128396998865227391 (1122 digits) 174516560225437653361964336594 ... 30820185220100243761843652461 (1911 digits) 489893405662883994748316933771 ... 74664296802930339234215909399 (1947 digits) 127469276849582096547381559312 ... 19580690153436989647994940101 (2283 digits) 357468265826587510126602192036 ... 69346589325010735912438195633 (3727 digits) 879871752812976577066489068488 ... 66056251048748727893681871587 (4270 digits) ^C (took too long)
Raku
sub abbr ($_) { (.chars < 41 ?? $_ !! .substr(0,20) ~ '..' ~ .substr(*-20)) ~ " (digits: {.chars})" }
say (++$).fmt('%2d') ~ ': ' ~ .flip.&abbr for (lazy (1,1,*+*…*).hyper.grep: {.flip.is-prime})[^25];
- Output:
1: 2 (digits: 1) 2: 3 (digits: 1) 3: 5 (digits: 1) 4: 31 (digits: 2) 5: 43 (digits: 2) 6: 773 (digits: 3) 7: 7951 (digits: 4) 8: 64901 (digits: 5) 9: 52057 (digits: 5) 10: 393121 (digits: 6) 11: 56577108676171 (digits: 14) 12: 940647607443258103531 (digits: 21) 13: 5237879497657222310489731409575442761 (digits: 37) 14: 9026258083384996860449366072142307801963 (digits: 40) 15: 19900335674812302969..34431012073266446403 (digits: 80) 16: 77841137362967479985..52312097783685331923 (digits: 104) 17: 37722585901567604188..29174997072830756131 (digits: 137) 18: 75736193894876131595..50767238644714305761 (digits: 330) 19: 17890336847332837620..13175300695235035913 (digits: 406) 20: 92327163101729115305..27061468856047302507 (digits: 409) 21: 50420157810698056253..67335124247362214481 (digits: 503) 22: 30511012474739380092..69296158361330018201 (digits: 888) 23: 46818547042693694555..08664543144645856321 (digits: 1020) 24: 87101347853037819884..20128396998865227391 (digits: 1122) 25: 17451656022543765336..20100243761843652461 (digits: 1911) 26: 48989340566288399474..02930339234215909399 (digits: 1947) 27: 12746927684958209654..53436989647994940101 (digits: 2283) 28: 35746826582658751012..25010735912438195633 (digits: 3727) 29: 87987175281297657706..48748727893681871587 (digits: 4270) 30: 81807376367113798363..13687506007959668569 (digits: 10527)
Wren
import "./gmp" for Mpz
import "./fmt" for Fmt
var fib = Mpz.new()
var p = Mpz.new()
var prev = Mpz.zero
var curr = Mpz.one
var count = 0
System.print("First 30 Iccanobif primes:")
while (count < 30) {
fib.add(curr, prev)
var fs = fib.toString
p.setStr(fs[-1..0])
if (p.probPrime(15) > 0) {
count = count + 1
var pc = p.toString.count
Fmt.print("$2d: $20a ($d digits)", count, p, pc)
}
prev.set(curr)
curr.set(fib)
}- Output:
First 30 Iccanobif primes: 1: 2 (1 digits) 2: 3 (1 digits) 3: 5 (1 digits) 4: 31 (2 digits) 5: 43 (2 digits) 6: 773 (3 digits) 7: 7951 (4 digits) 8: 64901 (5 digits) 9: 52057 (5 digits) 10: 393121 (6 digits) 11: 56577108676171 (14 digits) 12: 940647607443258103531 (21 digits) 13: 5237879497657222310489731409575442761 (37 digits) 14: 9026258083384996860449366072142307801963 (40 digits) 15: 19900335674812302969...34431012073266446403 (80 digits) 16: 77841137362967479985...52312097783685331923 (104 digits) 17: 37722585901567604188...29174997072830756131 (137 digits) 18: 75736193894876131595...50767238644714305761 (330 digits) 19: 17890336847332837620...13175300695235035913 (406 digits) 20: 92327163101729115305...27061468856047302507 (409 digits) 21: 50420157810698056253...67335124247362214481 (503 digits) 22: 30511012474739380092...69296158361330018201 (888 digits) 23: 46818547042693694555...08664543144645856321 (1020 digits) 24: 87101347853037819884...20128396998865227391 (1122 digits) 25: 17451656022543765336...20100243761843652461 (1911 digits) 26: 48989340566288399474...02930339234215909399 (1947 digits) 27: 12746927684958209654...53436989647994940101 (2283 digits) 28: 35746826582658751012...25010735912438195633 (3727 digits) 29: 87987175281297657706...48748727893681871587 (4270 digits) 30: 81807376367113798363...13687506007959668569 (10527 digits)