Magnanimous numbers: Difference between revisions
(→{{header|Pascal}}: changed Sieve of erathostenes in InitPrimes now TIO.RUN 5.5s instead of 22s at home 1.85s) |
SqrtNegInf (talk | contribs) m (→{{header|Pascal}}: restore visibility of Perl entry) |
||
| Line 1,927: | Line 1,927: | ||
563 6,464,886,245 |
563 6,464,886,245 |
||
564 9,151,995,592 |
564 9,151,995,592 |
||
0.795 s |
0.795 s</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Revision as of 02:56, 4 October 2021
You are encouraged to solve this task according to the task description, using any language you may know.
A magnanimous number is an integer where there is no place in the number where a + (plus sign) could be added between any two digits to give a non-prime sum.
- E.G.
- 6425 is a magnanimous number. 6 + 425 == 431 which is prime; 64 + 25 == 89 which is prime; 642 + 5 == 647 which is prime.
- 3538 is not a magnanimous number. 3 + 538 == 541 which is prime; 35 + 38 == 73 which is prime; but 353 + 8 == 361 which is not prime.
Traditionally the single digit numbers 0 through 9 are included as magnanimous numbers as there is no place in the number where you can add a plus between two digits at all. (Kind of weaselly but there you are...) Except for the actual value 0, leading zeros are not permitted. Internal zeros are fine though, 1001 -> 1 + 001 (prime), 10 + 01 (prime) 100 + 1 (prime).
There are only 571 known magnanimous numbers. It is strongly suspected, though not rigorously proved, that there are no magnanimous numbers above 97393713331910, the largest one known.
- Task
- Write a routine (procedure, function, whatever) to find magnanimous numbers.
- Use that function to find and display, here on this page the first 45 magnanimous numbers.
- Use that function to find and display, here on this page the 241st through 250th magnanimous numbers.
- Stretch: Use that function to find and display, here on this page the 391st through 400th magnanimous numbers
- See also
ALGOL 68
<lang algol68>BEGIN # find some magnanimous numbers - numbers where inserting a + between any #
# digits ab=nd evaluatinf the sum results in a prime in all cases #
# returns the first n magnanimous numbers #
# uses global sieve prime which must include 0 and be large enough #
# for all possible sub-sequences of digits #
OP MAGNANIMOUS = ( INT n )[]INT:
BEGIN
[ 1 : n ]INT result;
INT m count := 0;
FOR i FROM 0 WHILE m count < n DO
# split the number into pairs of digit seuences and check the sums of the pairs are all prime #
INT divisor := 1;
BOOL all prime := TRUE;
WHILE divisor *:= 10;
IF INT front = i OVER divisor;
front = 0
THEN FALSE
ELSE all prime := prime[ front + ( i MOD divisor ) ]
FI
DO SKIP OD;
IF all prime THEN result[ m count +:= 1 ] := i FI
OD;
result
END; # MAGNANIMPUS #
# prints part of a seuence of magnanimous numbers #
PROC print magnanimous = ( []INT m, INT first, INT last, STRING legend )VOID:
BEGIN
print( ( legend, ":", newline ) );
FOR i FROM first TO last DO print( ( " ", whole( m[ i ], 0 ) ) ) OD;
print( ( newline ) )
END ; # print magnanimous #
# we assume the first 400 magnanimous numbers will be in 0 .. 1 000 000 #
# so we will need a sieve of 0 up to 99 999 + 9 #
[ 0 : 99 999 + 9 ]BOOL prime;
prime[ 0 ] := prime[ 1 ] := FALSE; prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI
OD;
# construct the sequence of magnanimous numbers #
[]INT m = MAGNANIMOUS 400;
print magnanimous( m, 1, 45, "First 45 magnanimous numbers" );
print magnanimous( m, 241, 250, "Magnanimous numbers 241-250" );
print magnanimous( m, 391, 400, "Magnanimous numbers 391-400" )
END</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 Magnanimous numbers 241-250: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 Magnanimous numbers 391-400: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
ALGOL W
<lang algolw>begin
% find some Magnanimous numbers - numbers where inserting a "+" between %
% any two of the digits and evaluating the sum results in a prime number %
% implements the sieve of Eratosthenes %
procedure sieve( logical array s ( * ); integer value n ) ;
begin
% start with everything flagged as prime %
for i := 1 until n do s( i ) := true;
% sieve out the non-primes %
s( 1 ) := false;
for i := 2 until truncate( sqrt( n ) ) do begin
if s( i ) then for p := i * i step i until n do s( p ) := false
end for_i ;
end sieve ;
% construct an array of magnanimous numbers using the isPrime sieve %
procedure findMagnanimous ( logical array magnanimous, isPrime ( * ) ) ;
begin
% 1 digit magnanimous numbers %
for i := 0 until 9 do magnanimous( i ) := true;
% initially, the other magnanimous numbers are unknown %
for i := 10 until MAGNANIMOUS_MAX do magnanimous( i ) := false;
% 2 & 3 digit magnanimous numbers %
for d1 := 1 until 9 do begin
for d2 := 0 until 9 do begin
if isPrime( d1 + d2 ) then magnanimous( ( d1 * 10 ) + d2 ) := true
end for_d2 ;
for d23 := 0 until 99 do begin
if isPrime( d1 + d23 ) then begin
integer d12, d3;
d3 := d23 rem 10;
d12 := ( d1 * 10 ) + ( d23 div 10 );
if isPrime( d12 + d3 ) then magnanimous( ( d12 * 10 ) + d3 ) := true
end if_isPrime_d1_plus_d23
end for_d23
end for_d1 ;
% 4 & 5 digit magnanimous numbers %
for d12 := 10 until 99 do begin
for d34 := 0 until 99 do begin
if isPrime( d12 + d34 ) then begin
integer d123, d4;
d123 := ( d12 * 10 ) + ( d34 div 10 );
d4 := d34 rem 10;
if isPrime( d123 + d4 ) then begin
integer d1, d234;
d1 := d12 div 10;
d234 := ( ( d12 rem 10 ) * 100 ) + d34;
if isPrime( d1 + d234 ) then magnanimous( ( d12 * 100 ) + d34 ) := true
end if_isPrime_d123_plus_d4
end if_isPrime_d12_plus_d34
end for_d34 ;
for d345 := 0 until 999 do begin
if isPrime( d12 + d345 ) then begin
integer d123, d45;
d123 := ( d12 * 10 ) + ( d345 div 100 );
d45 := d345 rem 100;
if isPrime( d123 + d45 ) then begin
integer d1234, d5;
d1234 := ( d123 * 10 ) + ( d45 div 10 );
d5 := d45 rem 10;
if isPrime( d1234 + d5 ) then begin
integer d1, d2345;
d1 := d12 div 10;
d2345 := ( ( d12 rem 10 ) * 1000 ) + d345;
if isPrime( d1 + d2345 ) then magnanimous( ( d12 * 1000 ) + d345 ) := true
end if_isPrime_d1234_plus_d5
end if_isPrime_d123_plus_d45
end if_isPrime_d12_plus_d345
end for_d234
end for_d12 ;
% find 6 digit magnanimous numbers %
for d123 := 100 until 999 do begin
for d456 := 0 until 999 do begin
if isPrime( d123 + d456 ) then begin
integer d1234, d56;
d1234 := ( d123 * 10 ) + ( d456 div 100 );
d56 := d456 rem 100;
if isPrime( d1234 + d56 ) then begin
integer d12345, d6;
d12345 := ( d1234 * 10 ) + ( d56 div 10 );
d6 := d56 rem 10;
if isPrime( d12345 + d6 ) then begin
integer d12, d3456;
d12 := d123 div 10;
d3456 := ( ( d123 rem 10 ) * 1000 ) + d456;
if isPrime( d12 + d3456 ) then begin
integer d1, d23456;
d1 := d12 div 10;
d23456 := ( ( d12 rem 10 ) * 10000 ) + d3456;
if isPrime( d1 + d23456 ) then magnanimous( ( d123 * 1000 ) + d456 ) := true
end if_isPrime_d12_plus_d3456
end if_isPrime_d12345_plus_d6
end if_isPrime_d1234_plus_d56
end if_isPrime_d123_plus_d456
end for_d456
end for_d123
end findMagnanimous ;
% we look for magnanimous numbers with up to 6 digits, so we need to %
% check for primes up to 99999 + 9 = 100008 %
integer PRIME_MAX, MAGNANIMOUS_MAX;
PRIME_MAX := 100008;
MAGNANIMOUS_MAX := 1000000;
begin
logical array magnanimous ( 0 :: MAGNANIMOUS_MAX );
logical array isPrime ( 1 :: PRIME_MAX );
integer mPos;
integer lastM;
sieve( isPrime, PRIME_MAX );
findMagnanimous( magnanimous, isPrime );
% show some of the magnanimous numbers %
lastM := mPos := 0;
i_w := 3; s_w := 1; % output formatting %
for i := 0 until MAGNANIMOUS_MAX do begin
if magnanimous( i ) then begin
mPos := mPos + 1;
lastM := i;
if mPos = 1 then begin
write( "Magnanimous numbers 1-45:" );
write( i )
end
else if mPos < 46 then begin
if mPos rem 15 = 1 then write( i )
else writeon( i )
end
else if mPos = 241 then begin
write( "Magnanimous numbers 241-250:" );
write( i )
end
else if mPos > 241 and mPos <= 250 then writeon( i )
else if mPos = 391 then begin
write( "Magnanimous numbers 391-400:" );
write( i )
end
else if mPos > 391 and mPos <= 400 then writeon( i )
end if_magnanimous_i
end for_i ;
i_w := 1; s_w := 0;
write( "Last magnanimous number found: ", mPos, " = ", lastM )
end
end.</lang>
- Output:
Magnanimous numbers 1-45: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 Magnanimous numbers 241-250: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 Magnanimous numbers 391-400: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081 Last magnanimous number found: 434 = 999994
AWK
<lang AWK>
- syntax: GAWK -f MAGNANIMOUS_NUMBERS.AWK
- converted from C
BEGIN {
magnanimous(1,45) magnanimous(241,250) magnanimous(391,400) exit(0)
} function is_magnanimous(n, p,q,r) {
if (n < 10) { return(1) }
for (p=10; ; p*=10) {
q = int(n/p)
r = n % p
if (!is_prime(q+r)) { return(0) }
if (q < 10) { break }
}
return(1)
} function is_prime(n, d) {
d = 5
if (n < 2) { return(0) }
if (!(n % 2)) { return(n == 2) }
if (!(n % 3)) { return(n == 3) }
while (d*d <= n) {
if (!(n % d)) { return(0) }
d += 2
if (!(n % d)) { return(0) }
d += 4
}
return(1)
} function magnanimous(start,stop, count,i) {
printf("%d-%d:",start,stop)
for (i=0; count<stop; ++i) {
if (is_magnanimous(i)) {
if (++count >= start) {
printf(" %d",i)
}
}
}
printf("\n")
} </lang>
- Output:
1-45: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241-250: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391-400: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
C
<lang c>#include <stdio.h>
- include <string.h>
typedef int bool; typedef unsigned long long ull;
- define TRUE 1
- define FALSE 0
/* OK for 'small' numbers. */ bool is_prime(ull n) {
ull d;
if (n < 2) return FALSE;
if (!(n % 2)) return n == 2;
if (!(n % 3)) return n == 3;
d = 5;
while (d * d <= n) {
if (!(n % d)) return FALSE;
d += 2;
if (!(n % d)) return FALSE;
d += 4;
}
return TRUE;
}
void ord(char *res, int n) {
char suffix[3];
int m = n % 100;
if (m >= 4 && m <= 20) {
sprintf(res,"%dth", n);
return;
}
switch(m % 10) {
case 1:
strcpy(suffix, "st");
break;
case 2:
strcpy(suffix, "nd");
break;
case 3:
strcpy(suffix, "rd");
break;
default:
strcpy(suffix, "th");
break;
}
sprintf(res, "%d%s", n, suffix);
}
bool is_magnanimous(ull n) {
ull p, q, r;
if (n < 10) return TRUE;
for (p = 10; ; p *= 10) {
q = n / p;
r = n % p;
if (!is_prime(q + r)) return FALSE;
if (q < 10) break;
}
return TRUE;
}
void list_mags(int from, int thru, int digs, int per_line) {
ull i = 0;
int c = 0;
char res1[13], res2[13];
if (from < 2) {
printf("\nFirst %d magnanimous numbers:\n", thru);
} else {
ord(res1, from);
ord(res2, thru);
printf("\n%s through %s magnanimous numbers:\n", res1, res2);
}
for ( ; c < thru; ++i) {
if (is_magnanimous(i)) {
if (++c >= from) {
printf("%*llu ", digs, i);
if (!(c % per_line)) printf("\n");
}
}
}
}
int main() {
list_mags(1, 45, 3, 15); list_mags(241, 250, 1, 10); list_mags(391, 400, 1, 10); return 0;
}</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
C#
<lang csharp>using System; using static System.Console;
class Program {
static bool[] np; // not-prime array
static void ms(long lmt) { // populates array, a not-prime is true
np = new bool[lmt]; np[0] = np[1] = true;
for (long n = 2, j = 1; n < lmt; n += j, j = 2) if (!np[n])
for (long k = n * n; k < lmt; k += n) np[k] = true; }
static bool is_Mag(long n) { long res, rem;
for (long p = 10; n >= p; p *= 10) {
res = Math.DivRem (n, p, out rem);
if (np[res + rem]) return false; } return true; }
static void Main(string[] args) { ms(100_009); string mn;
WriteLine("First 45{0}", mn = " magnanimous numbers:");
for (long l = 0, c = 0; c < 400; l++) if (is_Mag(l)) {
if (c++ < 45 || (c > 240 && c <= 250) || c > 390)
Write(c <= 45 ? "{0,4} " : "{0,8:n0} ", l);
if (c < 45 && c % 15 == 0) WriteLine();
if (c == 240) WriteLine ("\n\n241st through 250th{0}", mn);
if (c == 390) WriteLine ("\n\n391st through 400th{0}", mn); } }
}</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17,992 19,972 20,209 20,261 20,861 22,061 22,201 22,801 22,885 24,407 391st through 400th magnanimous numbers: 486,685 488,489 515,116 533,176 551,558 559,952 595,592 595,598 600,881 602,081
C++
<lang cpp>#include <iomanip>
- include <iostream>
bool is_prime(unsigned int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (unsigned int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
bool is_magnanimous(unsigned int n) {
for (unsigned int p = 10; n >= p; p *= 10) {
if (!is_prime(n % p + n / p))
return false;
}
return true;
}
int main() {
unsigned int count = 0, n = 0;
std::cout << "First 45 magnanimous numbers:\n";
for (; count < 45; ++n) {
if (is_magnanimous(n)) {
if (count > 0)
std::cout << (count % 15 == 0 ? "\n" : ", ");
std::cout << std::setw(3) << n;
++count;
}
}
std::cout << "\n\n241st through 250th magnanimous numbers:\n";
for (unsigned int i = 0; count < 250; ++n) {
if (is_magnanimous(n)) {
if (count++ >= 240) {
if (i++ > 0)
std::cout << ", ";
std::cout << n;
}
}
}
std::cout << "\n\n391st through 400th magnanimous numbers:\n";
for (unsigned int i = 0; count < 400; ++n) {
if (is_magnanimous(n)) {
if (count++ >= 390) {
if (i++ > 0)
std::cout << ", ";
std::cout << n;
}
}
}
std::cout << '\n';
return 0;
}</lang>
- Output:
First 45 magnanimous numbers: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 20 21, 23, 25, 29, 30, 32, 34, 38, 41, 43, 47, 49, 50, 52, 56 58, 61, 65, 67, 70, 74, 76, 83, 85, 89, 92, 94, 98, 101, 110 241st through 250th magnanimous numbers: 17992, 19972, 20209, 20261, 20861, 22061, 22201, 22801, 22885, 24407 391st through 400th magnanimous numbers: 486685, 488489, 515116, 533176, 551558, 559952, 595592, 595598, 600881, 602081
F#
The function
This task uses Extensible Prime Generator (F#) <lang fsharp> // Generate Magnanimous numbers. Nigel Galloway: March 20th., 2020 let rec fN n g = match (g/n,g%n) with
(0,_) -> true
|(α,β) when isPrime (α+β) -> fN (n*10) g
|_ -> false
let Magnanimous = let Magnanimous = fN 10 in seq{yield! {0..9}; yield! Seq.initInfinite id |> Seq.skip 10 |> Seq.filter Magnanimous} </lang>
The Tasks
- First 45
<lang fsharp> Magnanimous |> Seq.take 45 |> Seq.iter (printf "%d "); printfn "" </lang>
- Output:
0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110
- Magnanimous[241] to Magnanimous[250]
<lang fsharp> Magnanimous |> Seq.skip 240 |> Seq.take 10 |> Seq.iter (printf "%d "); printfn "";; </lang>
- Output:
17992 19972 20209 20261 20861 22061 22201 22801 22885 24407
- Magnanimous[391] to Magnanimous[400]
<lang fsharp> Magnanimous |> Seq.skip 390 |> Seq.take 10 |> Seq.iter (printf "%d "); printfn "";; </lang>
- Output:
486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Factor
<lang factor>USING: grouping io kernel lists lists.lazy math math.functions math.primes math.ranges prettyprint sequences ;
- magnanimous? ( n -- ? )
dup 10 < [ drop t ] [
dup log10 >integer [1,b] [ 10^ /mod + prime? not ] with
find nip >boolean not
] if ;
- magnanimous ( n -- seq )
0 lfrom [ magnanimous? ] lfilter ltake list>array ;
- show ( seq from to -- ) rot subseq 15 group simple-table. nl ;
400 magnanimous [ "First 45 magnanimous numbers" print 0 45 show ] [ "241st through 250th magnanimous numbers" print 240 250 show ] [ "391st through 400th magnanimous numbers" print 390 400 show ] tri</lang>
- Output:
First 45 magnanimous numbers 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Go
<lang go>package main
import "fmt"
// OK for 'small' numbers. func isPrime(n uint64) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
default:
d := uint64(5)
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
func ord(n int) string {
m := n % 100
if m >= 4 && m <= 20 {
return fmt.Sprintf("%dth", n)
}
m %= 10
suffix := "th"
if m < 4 {
switch m {
case 1:
suffix = "st"
case 2:
suffix = "nd"
case 3:
suffix = "rd"
}
}
return fmt.Sprintf("%d%s", n, suffix)
}
func isMagnanimous(n uint64) bool {
if n < 10 {
return true
}
for p := uint64(10); ; p *= 10 {
q := n / p
r := n % p
if !isPrime(q + r) {
return false
}
if q < 10 {
break
}
}
return true
}
func listMags(from, thru, digs, perLine int) {
if from < 2 {
fmt.Println("\nFirst", thru, "magnanimous numbers:")
} else {
fmt.Printf("\n%s through %s magnanimous numbers:\n", ord(from), ord(thru))
}
for i, c := uint64(0), 0; c < thru; i++ {
if isMagnanimous(i) {
c++
if c >= from {
fmt.Printf("%*d ", digs, i)
if c%perLine == 0 {
fmt.Println()
}
}
}
}
}
func main() {
listMags(1, 45, 3, 15) listMags(241, 250, 1, 10) listMags(391, 400, 1, 10)
}</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Java
<lang java> import java.util.ArrayList; import java.util.List;
public class MagnanimousNumbers {
public static void main(String[] args) {
runTask("Find and display the first 45 magnanimous numbers.", 1, 45);
runTask("241st through 250th magnanimous numbers.", 241, 250);
runTask("391st through 400th magnanimous numbers.", 391, 400);
}
private static void runTask(String message, int startN, int endN) {
int count = 0;
List<Integer> nums = new ArrayList<>();
for ( int n = 0 ; count < endN ; n++ ) {
if ( isMagnanimous(n) ) {
nums.add(n);
count++;
}
}
System.out.printf("%s%n", message);
System.out.printf("%s%n%n", nums.subList(startN-1, endN));
}
private static boolean isMagnanimous(long n) {
if ( n >= 0 && n <= 9 ) {
return true;
}
long q = 11;
for ( long div = 10 ; q >= 10 ; div *= 10 ) {
q = n / div;
long r = n % div;
if ( ! isPrime(q+r) ) {
return false;
}
}
return true;
}
private static final int MAX = 100_000;
private static final boolean[] primes = new boolean[MAX];
private static boolean SIEVE_COMPLETE = false;
private static final boolean isPrimeTrivial(long test) {
if ( ! SIEVE_COMPLETE ) {
sieve();
SIEVE_COMPLETE = true;
}
return primes[(int) test];
}
private static final void sieve() {
// primes
for ( int i = 2 ; i < MAX ; i++ ) {
primes[i] = true;
}
for ( int i = 2 ; i < MAX ; i++ ) {
if ( primes[i] ) {
for ( int j = 2*i ; j < MAX ; j += i ) {
primes[j] = false;
}
}
}
}
// See http://primes.utm.edu/glossary/page.php?sort=StrongPRP public static final boolean isPrime(long testValue) { if ( testValue == 2 ) return true; if ( testValue % 2 == 0 ) return false; if ( testValue <= MAX ) return isPrimeTrivial(testValue); long d = testValue-1; int s = 0; while ( d % 2 == 0 ) { s += 1; d /= 2; } if ( testValue < 1373565L ) { if ( ! aSrp(2, s, d, testValue) ) { return false; } if ( ! aSrp(3, s, d, testValue) ) { return false; } return true; } if ( testValue < 4759123141L ) { if ( ! aSrp(2, s, d, testValue) ) { return false; } if ( ! aSrp(7, s, d, testValue) ) { return false; } if ( ! aSrp(61, s, d, testValue) ) { return false; } return true; } if ( testValue < 10000000000000000L ) { if ( ! aSrp(3, s, d, testValue) ) { return false; } if ( ! aSrp(24251, s, d, testValue) ) { return false; } return true; } // Try 5 "random" primes if ( ! aSrp(37, s, d, testValue) ) { return false; } if ( ! aSrp(47, s, d, testValue) ) { return false; } if ( ! aSrp(61, s, d, testValue) ) { return false; } if ( ! aSrp(73, s, d, testValue) ) { return false; } if ( ! aSrp(83, s, d, testValue) ) { return false; } //throw new RuntimeException("ERROR isPrime: Value too large = "+testValue); return true; }
private static final boolean aSrp(int a, int s, long d, long n) {
long modPow = modPow(a, d, n);
//System.out.println("a = "+a+", s = "+s+", d = "+d+", n = "+n+", modpow = "+modPow);
if ( modPow == 1 ) {
return true;
}
int twoExpR = 1;
for ( int r = 0 ; r < s ; r++ ) {
if ( modPow(modPow, twoExpR, n) == n-1 ) {
return true;
}
twoExpR *= 2;
}
return false;
}
private static final long SQRT = (long) Math.sqrt(Long.MAX_VALUE);
public static final long modPow(long base, long exponent, long modulus) {
long result = 1;
while ( exponent > 0 ) {
if ( exponent % 2 == 1 ) {
if ( result > SQRT || base > SQRT ) {
result = multiply(result, base, modulus);
}
else {
result = (result * base) % modulus;
}
}
exponent >>= 1;
if ( base > SQRT ) {
base = multiply(base, base, modulus);
}
else {
base = (base * base) % modulus;
}
}
return result;
}
// Result is a*b % mod, without overflow.
public static final long multiply(long a, long b, long modulus) {
long x = 0;
long y = a % modulus;
long t;
while ( b > 0 ) {
if ( b % 2 == 1 ) {
t = x + y;
x = (t > modulus ? t-modulus : t);
}
t = y << 1;
y = (t > modulus ? t-modulus : t);
b >>= 1;
}
return x % modulus;
}
} </lang>
- Output:
Find and display the first 45 magnanimous numbers. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 20, 21, 23, 25, 29, 30, 32, 34, 38, 41, 43, 47, 49, 50, 52, 56, 58, 61, 65, 67, 70, 74, 76, 83, 85, 89, 92, 94, 98, 101, 110] 241st through 250th magnanimous numbers. [17992, 19972, 20209, 20261, 20861, 22061, 22201, 22801, 22885, 24407] 391st through 400th magnanimous numbers. [486685, 488489, 515116, 533176, 551558, 559952, 595592, 595598, 600881, 602081]
J
write_sum_expressions=: ([: }: ]\) ,"1 '+' ,"1 ([: }. ]\.) NB. combine prefixes with suffixes
interstitial_sums=: ".@write_sum_expressions@":
primeQ=: 1&p:
magnanimousQ=: 1:`([: *./ [: primeQ interstitial_sums)@.(>&9)
A=: (#~ magnanimousQ&>) i.1000000 NB. filter 1000000 integers
#A
434
strange=: ({. + [: i. -~/)@:(_1 0&+) NB. produce index ranges for output
I=: _2 <@strange\ 1 45 241 250 391 400
I (":@:{~ >)~"0 _ A
0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110
17992 19972 20209 20261 20861 22061 22201 22801 22885 24407
486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
jq
Works with gojq, the Go implementation of jq
For a suitable definition of `is_prime`, see Erdős-primes#jq.
Preliminaries <lang jq># To take advantage of gojq's arbitrary-precision integer arithmetic: def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
def divrem($x; $y):
[$x/$y|floor, $x % $y];
</lang> The Task <lang jq> def ismagnanimous:
. as $n | if $n < 10 then true else first(range( 1; tostring|length) as $i
| divrem($n; (10|power($i))) as [$q, $r]
| if ($q + $r) | is_prime == false then 0 else empty end)
// true
| . == true
end;
- An unbounded stream ...
def magnanimous:
range(0; infinite) | select(ismagnanimous);
[limit(400; magnanimous)] | "First 45 magnanimous numbers:", .[:45],
"\n241st through 250th magnanimous numbers:", .[241:251], "\n391st through 400th magnanimous numbers:", .[391:]</lang>
- Output:
First 45 magnanimous numbers: [0,1,2,3,4,5,6,7,8,9,11,12,14,16,20,21,23,25,29,30,32,34,38,41,43,47,49,50,52,56,58,61,65,67,70,74,76,83,85,89,92,94,98,101,110] 241st through 250th magnanimous numbers: [19972,20209,20261,20861,22061,22201,22801,22885,24407,26201] 391st through 400th magnanimous numbers: [488489,515116,533176,551558,559952,595592,595598,600881,602081]
Julia
<lang julia>using Primes
function ismagnanimous(n)
n < 10 && return true
for i in 1:ndigits(n)-1
q, r = divrem(n, 10^i)
!isprime(q + r) && return false
end
return true
end
function magnanimous(N)
mvec, i = Int[], 0
while length(mvec) < N
if ismagnanimous(i)
push!(mvec, i)
end
i += 1
end
return mvec
end
const mag400 = magnanimous(400) println("First 45 magnanimous numbers:\n", mag400[1:24], "\n", mag400[25:45]) println("\n241st through 250th magnanimous numbers:\n", mag400[241:250]) println("\n391st through 400th magnanimous numbers:\n", mag400[391:400])
</lang>
- Output:
First 45 magnanimous numbers: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 20, 21, 23, 25, 29, 30, 32, 34, 38, 41] [43, 47, 49, 50, 52, 56, 58, 61, 65, 67, 70, 74, 76, 83, 85, 89, 92, 94, 98, 101, 110] 241st through 250th magnanimous numbers: [17992, 19972, 20209, 20261, 20861, 22061, 22201, 22801, 22885, 24407] 391st through 400th magnanimous numbers: [486685, 488489, 515116, 533176, 551558, 559952, 595592, 595598, 600881, 602081]
Mathematica/Wolfram Language
<lang Mathematica>Clear[MagnanimousNumberQ] MagnanimousNumberQ[Alternatives @@ Range[0, 9]] = True; MagnanimousNumberQ[n_Integer] := AllTrue[Range[IntegerLength[n] - 1], PrimeQ[Total[FromDigits /@ TakeDrop[IntegerDigits[n], #]]] &] sel = Select[Range[0, 1000000], MagnanimousNumberQ]; sel;; 45 sel241 ;; 250 sel391 ;; 400</lang>
- Output:
{0,1,2,3,4,5,6,7,8,9,11,12,14,16,20,21,23,25,29,30,32,34,38,41,43,47,49,50,52,56,58,61,65,67,70,74,76,83,85,89,92,94,98,101,110}
{17992,19972,20209,20261,20861,22061,22201,22801,22885,24407}
{486685,488489,515116,533176,551558,559952,595592,595598,600881,602081}
Nim
<lang Nim>func isPrime(n: Natural): bool =
if n < 2: return if n mod 2 == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 return true
func isMagnanimous(n: Natural): bool =
var p = 10 while true: let a = n div p let b = n mod p if a == 0: break if not isPrime(a + b): return false p *= 10 return true
iterator magnanimous(): (int, int) =
var n, count = 0
while true:
if n.isMagnanimous:
inc count
yield (count, n)
inc n
for (i, n) in magnanimous():
if i in 1..45: if i == 1: stdout.write "First 45 magnanimous numbers:\n " stdout.write n, if i == 45: '\n' else: ' '
elif i in 241..250: if i == 241: stdout.write "\n241st through 250th magnanimous numbers:\n " stdout.write n, if i == 250: "\n" else: " "
elif i in 391..400: if i == 391: stdout.write "\n391st through 400th magnanimous numbers:\n " stdout.write n, if i == 400: "\n" else: " "
elif i > 400: break</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Pascal
Version nearly like on Talk. Generating the sieve for primes takes most of the time.
found all til #564 : 9,151,995,592 in 0.795 s
<lang pascal>program Magnanimous;
//Magnanimous Numbers
//algorithm find only numbers where all digits are even except the last
//or where all digits are odd except the last
//Magnanimous Numbers that can not be found by this algorithm
//0,1,11,20,101,1001
{$IFDEF FPC}
{$MODE DELPHI}
{$Optimization ON,ALL}
{$CODEALIGN proc=16}
{$ENDIF} uses
strUtils,SysUtils;
const
MaxLimit = 1000*1000*1000;
type
tprimes = array of byte; tBaseType = word; tpBaseType = pWord; tBase =array[0..15] of tBaseType;
tNumType = NativeUint; tSplitNum =array[0..15] of tNumType; tMagList = array[0..571] of Uint64;
var
{$ALIGN 32}
dgtBase5,
dgtEvenBase10,
dgtOddBase10: tbase;
MagList : tMagList;
primes : tprimes;
pPrimes0 : pByte;
T0: int64;
HighIdx,lstIdx, cnt,num,MagIdx: NativeUint;
procedure InsertSort(pMag:pUint64; Left, Right : NativeInt );
var
I, J: NativeInt;
Pivot : Uint64;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pMag[i];
j:= i - 1;
while (j >= Left) and (pMag[j] > Pivot) do
begin
pMag[j+1]:=pMag[j];
Dec(j);
end;
pMag[j+1]:= pivot;
end;
end;
procedure InitPrimes;
const
smallprimes :array[0..5] of byte = (2,3,5,7,11,13);
var
pPrimes : pByte;
p,i,j,l : NativeUint;
begin
l := 1;
for j := 0 to High(smallprimes) do
l*= smallprimes[j];
//scale primelimit to be multiple of l
i :=((MaxLimit-1) DIV l+1)*l+1;//+1 should suffice
setlength(primes,i);
pPrimes := @primes[0];
for j := 0 to High(smallprimes) do
begin
p := smallprimes[j];
i := p;
if j <> 0 then
p +=p;
while i <= l do
begin
pPrimes[i] := 1;
inc(i,p)
end;
end;
//turn the prime wheel
for p := length(primes) div l -1 downto 1 do
move(pPrimes[1],pPrimes[p*l+1],l);
l := High(primes);
//reinsert smallprimes
for j := 0 to High(smallprimes) do
pPrimes[smallprimes[j]] := 0;
pPrimes[1]:=1;
pPrimes[0]:=1;
p := smallprimes[High(smallprimes)];
//sieve with next primes
repeat
repeat
inc(p,2)
until pPrimes[p] = 0;
//j = maxfactor of p in l
j := l div p;
// make j prime
while (pPrimes[j]<> 0) AND (j>=p) do
dec(j);
if j
= 5 //to minimize memory accesses in deep space... i := (j+1) mod 6; if i = 0 then i :=4; repeat //search next prime factor while (pPrimes[j]<> 0) AND (j>=p) do begin dec(j,i); i := 6-i; end; if j<p then BREAK; //access far memory , unmark prime . pPrimes[j*p] := 1; dec(j,i); i := 6-i; until j<p; until false; pPrimes0 := pPrimes; end; procedure OutBase5; var pb: tpBaseType; i : NativeUint; begin pb:= @dgtBase5[0]; for i := HighIdx downto 0 do write(pB[i]:2); writeln; end; function IncDgtBase5:nativeUint; var pb: tpBaseType; num: nativeint; begin pb:= @dgtBase5[0]; result := 0; repeat num := pb[result] + 1; if num < 5 then begin pb[result] := num; break; end; pb[result] := 0; Inc(result); until False; if HighIdx < result then begin HighIdx := result; pb[result] := 0; end; end; procedure CnvEvenBase10(lastIdx:NativeInt); var pdgt : tpBaseType; idx: nativeint; begin pDgt := @dgtEvenBase10[0]; for idx := lastIdx downto 1 do pDgt[idx] := 2 * dgtBase5[idx]; pDgt[0] := 2 * dgtBase5[0]+1; end; procedure CnvOddBase10(lastIdx:NativeInt); var pdgt : tpBaseType; idx: nativeint; begin pDgt := @dgtOddBase10[0]; for idx := lastIdx downto 1 do pDgt[idx] := 2 * dgtBase5[idx] + 1; pDgt[0] := 2 * dgtBase5[0]; end; function Base10toNum(var dgtBase10: tBase):NativeUint; var i : NativeInt; begin Result := 0; for i := HighIdx downto 0 do Result := Result * 10 + dgtBase10[i]; end; function isMagn(var dgtBase10: tBase):boolean; //split number into sum of all "partitions" of digits //check if sum is always prime //1234 -> 1+234,12+34 ; 123+4 var LowSplitNum // ,HighSplitNum //not needed for small numbers :tSplitNum; i,fac,n: NativeInt; Begin n := 0; fac := 1; For i := 0 to HighIdx-1 do begin n := fac*dgtBase10[i]+n; fac *=10; LowSplitNum[HighIdx-1-i] := n; end; n := 0; fac := HighIdx; result := true; For i := 0 to fac-1 do begin n := n*10+dgtBase10[fac-i]; //HighSplitNum[i]:= n; result := result AND ( pPrimes0[LowSplitNum[i] +n] = 0); IF not(result) then break; end; end; begin T0 := Gettickcount64; InitPrimes; T0 -= Gettickcount64; writeln('getting primes ',-T0 / 1000: 0: 3, ' s'); T0 := Gettickcount64; fillchar(dgtBase5,SizeOf(dgtBase5),#0); fillchar(dgtEvenBase10,SizeOf(dgtEvenBase10),#0); fillchar(dgtOddBase10,SizeOf(dgtOddBase10),#0); //Magnanimous Numbers that can not be found by this algorithm MagIdx := 0; MagList[MagIdx] := 1;inc(MagIdx); MagList[MagIdx] := 11;inc(MagIdx); MagList[MagIdx] := 20;inc(MagIdx); MagList[MagIdx] := 101;inc(MagIdx); MagList[MagIdx] := 1001;inc(MagIdx); HighIdx := 0; lstIdx := 0; repeat if dgtBase5[highIdx] <> 0 then begin CnvEvenBase10(lstIdx); num := Base10toNum(dgtEvenBase10); if isMagn(dgtEvenBase10)then Begin MagList[MagIdx] := num; inc(MagIdx); // write(num:10,' ');OutBase5; end; end; CnvOddBase10(lstIdx); num := Base10toNum(dgtOddBase10); if isMagn(dgtOddBase10) then Begin MagList[MagIdx] := num; inc(MagIdx); // write(num:10,' ');OutBase5; end; lstIdx := IncDgtBase5; until HighIdx > trunc(ln(MaxLimit)/ln(10)); InsertSort(@MagList[0],0,MagIdx-1); For cnt := 0 to MagIdx-1 do writeln(cnt+1:3,' ',Numb2USA(IntToStr(MagList[cnt]))); T0 -= Gettickcount64; writeln(-T0 / 1000: 0: 3, ' s'); {$IFDEF Windows} readln; {$ENDIF} end. </lang>
- Output:
TIO.RUN // copied last lines 564 9,151,995,592--0.795 s //Real time: 6.936 s User time: 4.921 s Sys. time: 1.843 s CPU share: 97.51 % getting primes 5.530 s 1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 11 12 12 13 14 14 16 15 20 16 21 17 23 18 25 19 29 20 30 21 32 22 34 23 38 24 41 25 43 26 47 27 49 28 50 29 52 30 56 31 58 32 61 33 65 34 67 35 70 36 74 37 76 38 83 39 85 40 89 41 92 42 94 43 98 44 101 45 110 46 112 47 116 48 118 49 130 50 136 51 152 52 158 53 170 54 172 55 203 56 209 57 221 58 227 59 229 60 245 61 265 62 281 63 310 64 316 65 334 66 338 67 356 68 358 69 370 70 376 71 394 72 398 73 401 74 403 75 407 76 425 77 443 78 449 79 467 80 485 81 512 82 518 83 536 84 538 85 554 86 556 87 574 88 592 89 598 90 601 91 607 92 625 93 647 94 661 95 665 96 667 97 683 98 710 99 712 100 730 101 736 102 754 103 772 104 776 105 790 106 794 107 803 108 809 109 821 110 845 111 863 112 881 113 889 114 934 115 938 116 952 117 958 118 970 119 974 120 992 121 994 122 998 123 1,001 124 1,112 125 1,130 126 1,198 127 1,310 128 1,316 129 1,598 130 1,756 131 1,772 132 1,910 133 1,918 134 1,952 135 1,970 136 1,990 137 2,209 138 2,221 139 2,225 140 2,249 141 2,261 142 2,267 143 2,281 144 2,429 145 2,447 146 2,465 147 2,489 148 2,645 149 2,681 150 2,885 151 3,110 152 3,170 153 3,310 154 3,334 155 3,370 156 3,398 157 3,518 158 3,554 159 3,730 160 3,736 161 3,794 162 3,934 163 3,974 164 4,001 165 4,027 166 4,063 167 4,229 168 4,247 169 4,265 170 4,267 171 4,427 172 4,445 173 4,463 174 4,643 175 4,825 176 4,883 177 5,158 178 5,176 179 5,374 180 5,516 181 5,552 182 5,558 183 5,594 184 5,752 185 5,972 186 5,992 187 6,001 188 6,007 189 6,067 190 6,265 191 6,403 192 6,425 193 6,443 194 6,485 195 6,601 196 6,685 197 6,803 198 6,821 199 7,330 200 7,376 201 7,390 202 7,394 203 7,534 204 7,556 205 7,592 206 7,712 207 7,934 208 7,970 209 8,009 210 8,029 211 8,221 212 8,225 213 8,801 214 8,821 215 9,118 216 9,172 217 9,190 218 9,338 219 9,370 220 9,374 221 9,512 222 9,598 223 9,710 224 9,734 225 9,752 226 9,910 227 11,116 228 11,152 229 11,170 230 11,558 231 11,930 232 13,118 233 13,136 234 13,556 235 15,572 236 15,736 237 15,938 238 15,952 239 17,716 240 17,752 241 17,992 242 19,972 243 20,209 244 20,261 245 20,861 246 22,061 247 22,201 248 22,801 249 22,885 250 24,407 251 26,201 252 26,285 253 26,881 254 28,285 255 28,429 256 31,370 257 31,756 258 33,118 259 33,538 260 33,554 261 35,116 262 35,776 263 37,190 264 37,556 265 37,790 266 37,930 267 39,158 268 39,394 269 40,001 270 40,043 271 40,049 272 40,067 273 40,427 274 40,463 275 40,483 276 42,209 277 42,265 278 44,009 279 44,443 280 44,447 281 46,445 282 48,089 283 48,265 284 51,112 285 53,176 286 53,756 287 53,918 288 55,516 289 55,552 290 55,558 291 55,576 292 55,774 293 57,116 294 57,754 295 60,007 296 60,047 297 60,403 298 60,443 299 60,667 300 62,021 301 62,665 302 64,645 303 66,667 304 66,685 305 68,003 306 68,683 307 71,536 308 71,572 309 71,716 310 71,752 311 73,156 312 75,374 313 75,556 314 77,152 315 77,554 316 79,330 317 79,370 318 80,009 319 80,029 320 80,801 321 80,849 322 82,265 323 82,285 324 82,825 325 82,829 326 84,265 327 86,081 328 86,221 329 88,061 330 88,229 331 88,265 332 88,621 333 91,792 334 93,338 335 93,958 336 93,994 337 99,712 338 99,998 339 111,112 340 111,118 341 111,170 342 111,310 343 113,170 344 115,136 345 115,198 346 115,772 347 117,116 348 119,792 349 135,158 350 139,138 351 151,156 352 151,592 353 159,118 354 177,556 355 193,910 356 199,190 357 200,209 358 200,809 359 220,021 360 220,661 361 222,245 362 224,027 363 226,447 364 226,681 365 228,601 366 282,809 367 282,881 368 282,889 369 311,156 370 319,910 371 331,118 372 333,770 373 333,994 374 335,156 375 339,370 376 351,938 377 359,794 378 371,116 379 373,130 380 393,554 381 399,710 382 400,049 383 404,249 384 408,049 385 408,889 386 424,607 387 440,843 388 464,447 389 484,063 390 484,445 391 486,685 392 488,489 393 515,116 394 533,176 395 551,558 396 559,952 397 595,592 398 595,598 399 600,881 400 602,081 401 626,261 402 628,601 403 644,485 404 684,425 405 686,285 406 711,512 407 719,710 408 753,316 409 755,156 410 773,554 411 777,712 412 777,776 413 799,394 414 799,712 415 800,483 416 802,061 417 802,081 418 804,863 419 806,021 420 806,483 421 806,681 422 822,265 423 864,883 424 888,485 425 888,601 426 888,643 427 911,390 428 911,518 429 915,752 430 931,130 431 975,772 432 979,592 433 991,118 434 999,994 435 1,115,756 436 1,137,770 437 1,191,518 438 1,197,370 439 1,353,136 440 1,379,930 441 1,533,736 442 1,593,538 443 1,711,576 444 1,791,110 445 1,795,912 446 1,915,972 447 1,951,958 448 2,000,221 449 2,008,829 450 2,442,485 451 2,604,067 452 2,606,647 453 2,664,425 454 2,666,021 455 2,828,809 456 2,862,445 457 3,155,116 458 3,171,710 459 3,193,198 460 3,195,338 461 3,195,398 462 3,315,358 463 3,373,336 464 3,573,716 465 3,737,534 466 3,751,576 467 3,939,118 468 4,000,483 469 4,408,603 470 4,468,865 471 4,488,245 472 4,644,407 473 5,115,736 474 5,357,776 475 5,551,376 476 5,579,774 477 5,731,136 478 5,759,594 479 5,959,774 480 6,462,667 481 6,600,227 482 6,600,443 483 6,608,081 484 6,640,063 485 6,640,643 486 6,824,665 487 6,864,485 488 6,866,683 489 7,113,710 490 7,133,110 491 7,139,390 492 7,153,336 493 7,159,172 494 7,311,170 495 7,351,376 496 7,719,370 497 7,959,934 498 7,979,534 499 8,044,009 500 8,068,201 501 8,608,081 502 8,844,449 503 9,171,170 504 9,777,910 505 9,959,374 506 11,771,992 507 13,913,170 508 15,177,112 509 17,115,116 510 19,337,170 511 19,713,130 512 20,266,681 513 22,086,821 514 22,600,601 515 22,862,885 516 26,428,645 517 28,862,465 518 33,939,518 519 37,959,994 520 40,866,083 521 44,866,043 522 48,606,043 523 48,804,809 524 51,137,776 525 51,513,118 526 53,151,376 527 53,775,934 528 59,593,574 529 60,402,247 530 60,860,603 531 62,202,281 532 64,622,665 533 66,864,625 534 66,886,483 535 71,553,536 536 77,917,592 537 82,486,825 538 86,842,265 539 91,959,398 540 95,559,998 541 117,711,170 542 222,866,845 543 228,440,489 544 244,064,027 545 280,422,829 546 331,111,958 547 400,044,049 548 460,040,803 549 511,151,552 550 593,559,374 551 606,202,627 552 608,844,043 553 622,622,801 554 622,888,465 555 773,719,910 556 844,460,063 557 882,428,665 558 995,955,112 559 1,777,137,770 560 2,240,064,227 561 2,444,402,809 562 5,753,779,594 563 6,464,886,245 564 9,151,995,592 0.795 s
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'is_prime';
sub magnanimous {
my($n) = @_;
my $last;
for my $c (1 .. length($n) - 1) {
++$last and last unless is_prime substr($n,0,$c) + substr($n,$c)
}
not $last;
}
my @M; for ( my $i = 0, my $count = 0; $count < 400; $i++ ) {
++$count and push @M, $i if magnanimous($i);
}
say "First 45 magnanimous numbers\n".
(sprintf "@{['%4d' x 45]}", @M[0..45-1]) =~ s/(.{60})/$1\n/gr;
say "241st through 250th magnanimous numbers\n" .
join ' ', @M[240..249];
say "\n391st through 400th magnanimous numbers\n".
join ' ', @M[390..399];</lang>
- Output:
First 45 magnanimous numbers 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Phix
with javascript_semantics function magnanimous(integer n) integer p = 1, r = 0 while n>=10 do r += remainder(n,10)*p n = floor(n/10) if not is_prime(n+r) then return false end if p *= 10 end while return true end function sequence mag = {} integer n = 0 while length(mag)<400 do if magnanimous(n) then mag &= n end if n += 1 end while puts(1,"First 45 magnanimous numbers: ") pp(mag[1..45],{pp_Indent,30,pp_IntCh,false,pp_Maxlen,100}) printf(1,"magnanimous numbers[241..250]: %v\n", {mag[241..250]}) printf(1,"magnanimous numbers[391..400]: %v\n", {mag[391..400]})
- Output:
First 45 magnanimous numbers: {0,1,2,3,4,5,6,7,8,9,11,12,14,16,20,21,23,25,29,30,32,34,38,41,43,
47,49,50,52,56,58,61,65,67,70,74,76,83,85,89,92,94,98,101,110}
magnanimous numbers[241..250]: {17992,19972,20209,20261,20861,22061,22201,22801,22885,24407}
magnanimous numbers[391..400]: {486685,488489,515116,533176,551558,559952,595592,595598,600881,602081}
PicoLisp
<lang PicoLisp>(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
(de isprime (N)
(cache '(NIL) N
(if (== N 2)
T
(and
(> N 1)
(bit? 1 N)
(let (Q (dec N) N1 (dec N) K 0 X)
(until (bit? 1 Q)
(setq
Q (>> 1 Q)
K (inc K) ) )
(catch 'composite
(do 16
(loop
(setq X
(**Mod
(rand 2 (min (dec N) 1000000000000))
Q
N ) )
(T (or (=1 X) (= X N1)))
(T
(do K
(setq X (**Mod X 2 N))
(when (=1 X) (throw 'composite))
(T (= X N1) T) ) )
(throw 'composite) ) )
(throw 'composite T) ) ) ) ) ) )
(de numbers (N)
(let (P 10 Q N)
(make
(until (> 10 Q)
(link
(+
(setq Q (/ N P))
(% N P) ) )
(setq P (* P 10)) ) ) ) )
(de ismagna (N)
(or
(> 10 N)
(fully isprime (numbers N)) ) )
(let (C 0 N 0 Lst)
(setq Lst
(make
(until (== C 401)
(when (ismagna N)
(link N)
(inc 'C) )
(inc 'N) ) ) )
(println (head 45 Lst))
(println (head 10 (nth Lst 241)))
(println (head 10 (nth Lst 391))) )</lang>
- Output:
(0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110) (17992 19972 20209 20261 20861 22061 22201 22801 22885 24407) (486685 488489 515116 533176 551558 559952 595592 595598 600881 602081)
PL/M
This sample can be compiled with the original 8080 PL/M compiler and run under CP/M (or a clone/emulator).
THe original 8080 PL/M only supports 8 and 16 bit quantities, so this only shows magnanimous numbers up to the 250th.
<lang plm>100H: /* FIND SOME MAGNANIMOUS NUMBERS - THOSE WHERE INSERTING '+' BETWEEN */
/* ANY TWO OF THE DIGITS AND EVALUATING THE SUM RESULTS IN A PRIME */
BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */
DECLARE FN BYTE, ARG ADDRESS;
GOTO 5;
END BDOS;
PRINT$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PRINT$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PRINT$NL: PROCEDURE; CALL PRINT$STRING( .( 0DH, 0AH, '$' ) ); END;
PRINT$NUMBER: PROCEDURE( N );
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
IF N < 100 THEN DO;
IF N < 10 THEN CALL PRINT$CHAR( ' ' );
CALL PRINT$CHAR( ' ' );
END;
CALL PRINT$STRING( .N$STR( W ) );
END PRINT$NUMBER;
/* INTEGER SQUARE ROOT: BASED ON THE ONE IN THE PL/M FROBENIUS NUMBERS */
SQRT: PROCEDURE( N )ADDRESS;
DECLARE ( N, X0, X1 ) ADDRESS;
IF N <= 3 THEN DO;
IF N = 0 THEN X0 = 0; ELSE X0 = 1;
END;
ELSE DO;
X0 = SHR( N, 1 );
DO WHILE( ( X1 := SHR( X0 + ( N / X0 ), 1 ) ) < X0 );
X0 = X1;
END;
END;
RETURN X0;
END SQRT;
DECLARE MAGNANIMOUS (251)ADDRESS; /* MAGNANIMOUS NUMBERS */
DECLARE FALSE LITERALLY '0';
DECLARE TRUE LITERALLY '0FFH';
/* TO FIND MAGNANIMOUS NUMBERS UP TO 30$000, WE NEED TO FIND PRIMES */
/* UP TO 9$999 + 9 = 10$008 */
DECLARE MAX$PRIME LITERALLY '10$008';
DECLARE DCL$PRIME LITERALLY '10$009';
/* SIEVE THE PRIMES TO MAX$PRIME */
DECLARE ( I, S ) ADDRESS;
DECLARE PRIME ( DCL$PRIME )BYTE;
PRIME( 1 ) = FALSE; PRIME( 2 ) = TRUE;
DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END;
DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;
DO I = 3 TO SQRT( MAX$PRIME );
IF PRIME( I ) THEN DO;
DO S = I * I TO LAST( PRIME ) BY I + I;PRIME( S ) = FALSE; END;
END;
END;
/* FIND THE MAGNANIMOUS NUMBERS */
FIND$MAGNANIMOUS: PROCEDURE;
DECLARE ( D1, D2, D3, D4, D5
, D12, D123, D1234
, D23, D234, D2345
, D34, D345, D45
) ADDRESS;
DECLARE M$COUNT ADDRESS; /* COUNT OF MAGNANIMOUS NUMBERS FOUND */
STORE$MAGNANIMOUS: PROCEDURE( N )BYTE;
DECLARE N ADDRESS;
M$COUNT = M$COUNT + 1;
IF M$COUNT <= LAST( MAGNANIMOUS ) THEN MAGNANIMOUS( M$COUNT ) = N;
RETURN M$COUNT <= LAST( MAGNANIMOUS );
END STORE$MAGNANIMOUS;
M$COUNT = 0;
/* 1 DIGIT MAGNANIMOUS NUMBERS */
DO D1 = 0 TO 9; IF NOT STORE$MAGNANIMOUS( D1 ) THEN RETURN; END;
/* 2 DIGIT MAGNANIMOUS NUMBERS */
DO D1 = 1 TO 9;
DO D2 = 0 TO 9;
IF PRIME( D1 + D2 ) THEN DO;
IF NOT STORE$MAGNANIMOUS( ( D1 * 10 ) + D2 ) THEN RETURN;
END;
END;
END;
/* 3 DIGIT MAGNANIMOUS NUMBERS */
DO D1 = 1 TO 9;
DO D23 = 0 TO 99;
IF PRIME( D1 + D23 ) THEN DO;
D3 = D23 MOD 10;
D12 = ( D1 * 10 ) + ( D23 / 10 );
IF PRIME( D12 + D3 ) THEN DO;
IF NOT STORE$MAGNANIMOUS( ( D12 * 10 ) + D3 ) THEN RETURN;
END;
END;
END;
END;
/* 4 DIGIT MAGNANIMOUS NUMBERS */
DO D12 = 10 TO 99;
DO D34 = 0 TO 99;
IF PRIME( D12 + D34 ) THEN DO;
D123 = ( D12 * 10 ) + ( D34 / 10 );
D4 = D34 MOD 10;
IF PRIME( D123 + D4 ) THEN DO;
D1 = D12 / 10;
D234 = ( ( D12 MOD 10 ) * 100 ) + D34;
IF PRIME( D1 + D234 ) THEN DO;
IF NOT STORE$MAGNANIMOUS( ( D12 * 100 ) + D34 )
THEN RETURN;
END;
END;
END;
END;
END;
/* 5 DIGIT MAGNANIMOUS NUMBERS UP TO 30$000 */
DO D12 = 10 TO 30;
DO D345 = 0 TO 999;
IF PRIME( D12 + D345 ) THEN DO;
D123 = ( D12 * 10 ) + ( D345 / 100 );
D45 = D345 MOD 100;
IF PRIME( D123 + D45 ) THEN DO;
D1234 = ( D123 * 10 ) + ( D45 / 10 );
D5 = D45 MOD 10;
IF PRIME( D1234 + D5 ) THEN DO;
D1 = D12 / 10;
D2345 = ( ( D12 MOD 10 ) * 1000 ) + D345;
IF PRIME( D1 + D2345 ) THEN DO;
IF NOT STORE$MAGNANIMOUS( ( D12 * 1000 ) + D345 )
THEN RETURN;
END;
END;
END;
END;
END;
END;
END FIND$MAGNANIMOUS ;
CALL FIND$MAGNANIMOUS;
DO I = 1 TO LAST( MAGNANIMOUS );
IF I = 1 THEN DO;
CALL PRINT$STRING( .'MAGNANIMOUS NUMBERS 1-45:$' ); CALL PRINT$NL;
CALL PRINT$NUMBER( MAGNANIMOUS( I ) );
END;
ELSE IF I < 46 THEN DO;
IF I MOD 15 = 1 THEN CALL PRINT$NL; ELSE CALL PRINT$CHAR( ' ' );
CALL PRINT$NUMBER( MAGNANIMOUS( I ) );
END;
ELSE IF I = 241 THEN DO;
CALL PRINT$NL;
CALL PRINT$STRING( .'MAGANIMOUS NUMBERS 241-250:$' ); CALL PRINT$NL;
CALL PRINT$NUMBER( MAGNANIMOUS( I ) );
END;
ELSE IF I > 241 AND I <= 250 THEN DO;
CALL PRINT$CHAR( ' ' );
CALL PRINT$NUMBER( MAGNANIMOUS( I ) );
END;
END;
CALL PRINT$NL;
EOF</lang>
- Output:
MAGNANIMOUS NUMBERS 1-45: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 MAGANIMOUS NUMBERS 241-250: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407
Raku
<lang perl6>my @magnanimous = lazy flat ^10, (10 .. 1001).map( {
my int $last;
(1 ..^ .chars).map: -> \c { $last = 1 and last unless (.substr(0,c) + .substr(c)).is-prime }
next if $last;
$_
} ),
(1002 .. ∞).map: {
# optimization for numbers > 1001; First and last digit can not both be even or both be odd
next if (.substr(0,1) + .substr(*-1)) %% 2;
my int $last;
(1 ..^ .chars).map: -> \c { $last = 1 and last unless (.substr(0,c) + .substr(c)).is-prime }
next if $last;
$_
}
put 'First 45 magnanimous numbers'; put @magnanimous[^45]».fmt('%3d').batch(15).join: "\n";
put "\n241st through 250th magnanimous numbers"; put @magnanimous[240..249];
put "\n391st through 400th magnanimous numbers"; put @magnanimous[390..399];</lang>
- Output:
First 45 magnanimous numbers 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
REXX
The majority of the time consumed was in generating a list (sparse array) of suitable primes.
The magna function (magnanimous) was quite simple to code and pretty fast, it includes the 1st and last digit parity test.
By far, the most CPU time was in the generation of primes.
<lang REXX>/*REXX pgm finds/displays magnanimous #s (#s with a inserted + sign to sum to a prime).*/
parse arg bet.1 bet.2 bet.3 highP . /*obtain optional arguments from the CL*/
if bet.1== | bet.1=="," then bet.1= 1..45 /* " " " " " " */
if bet.2== | bet.2=="," then bet.2= 241..250 /* " " " " " " */
if bet.3== | bet.3=="," then bet.3= 391..400 /* " " " " " " */
if highP== | highP=="," then highP= 1000000 /* " " " " " " */
call genP /*gen primes up to highP (1 million).*/
do j=1 for 3 /*process three magnanimous "ranges". */
parse var bet.j LO '..' HI /*obtain the first range (if any). */
if HI== then HI= LO /*Just a single number? Then use LO. */
if HI==0 then iterate /*Is HI a zero? Then skip this range.*/
finds= 0; $= /*#: magnanimous # cnt; $: is a list*/
do k=0 until finds==HI /* [↓] traipse through the number(s). */
if \magna(k) then iterate /*Not magnanimous? Then skip this num.*/
finds= finds + 1 /*bump the magnanimous number count. */
if finds>=LO then $= $ k /*In range► Then add number ──► $ list*/
end /*k*/
say
say center(' 'LO "──►" HI 'magnanimous numbers ', 126, "─")
say strip($)
end /*j*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ magna: procedure expose @. !.; parse arg x 1 L 2 -1 R /*obtain #, 1st & last digit.*/
len= length(x); if len==1 then return 1 /*one digit #s are magnanimous*/
if x>1001 then if L//2 == R//2 then return 0 /*Has parity? Not magnanimous*/
do s= 1 for len-1 /*traipse thru #, inserting + */
parse var x y +(s) z; sum= y + z /*parse 2 parts of #, sum 'em.*/
if !.sum then iterate /*Is sum prime? So far so good*/
else return 0 /*Nope? Then not magnanimous.*/
end /*s*/
return 1 /*Pass all the tests, it's magnanimous.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13 /*assign low primes; # primes.*/
!.= 0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1 /* " semaphores to " */
#= 6; sq.#= @.# ** 2 /*# primes so far; P squared.*/
do j=@.#+4 by 2 to highP; parse var j -1 _; if _==5 then iterate /*÷ by 5?*/
if j// 3==0 then iterate; if j// 7==0 then iterate /*÷ by 3?; ÷ by 7?*/
if j//11==0 then iterate /*" " 11? " " 13?*/
do k=6 while sq.k<=j /*divide by some generated odd primes. */
if j//@.k==0 then iterate j /*Is J divisible by P? Then not prime*/
end /*k*/ /* [↓] a prime (J) has been found. */
#= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump #Ps; P──►@.assign P; P^2; P flag*/
end /*j*/; return</lang>
- output when using the default inputs:
──────────────────────────────────────────────── 1 ──► 45 magnanimous numbers ──────────────────────────────────────────────── 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 and took 0.00 seconds. ────────────────────────────────────────────── 241 ──► 250 magnanimous numbers ─────────────────────────────────────────────── 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 and took 0.31 seconds. ────────────────────────────────────────────── 391 ──► 400 magnanimous numbers ─────────────────────────────────────────────── 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Ring
<lang ring> load "stdlib.ring" n = -1 sum = 0 magn = []
while sum < 45
n = n + 1
if n < 10
add(magn,n)
sum = sum + 1
else
nStr = string(n)
check = 0
for m = 1 to len(nStr)-1
nr1 = number(left(nStr,m))
nr2 = number(right(nStr,len(nStr)-m))
nr3 = nr1 + nr2
if not isprime(nr3)
check = 1
ok
next
if check = 0
add(magn,n)
sum = sum + 1
ok
ok
end
see "Magnanimous numbers 1-45:" + nl showArray(magn)
n = -1 sum = 0 magn = []
while sum < 250
n = n + 1
if n < 10
sum = sum + 1
else
nStr = string(n)
check = 0
for m = 1 to len(nStr)-1
nr1 = number(left(nStr,m))
nr2 = number(right(nStr,len(nStr)-m))
nr3 = nr1 + nr2
if not isprime(nr3)
check = 1
ok
next
if check = 0
sum = sum + 1
ok
if check = 0 and sum > 240 and sum < 251
add(magn,n)
ok
ok
end
see nl see "Magnanimous numbers 241-250:" + nl showArray(magn)
func showArray array
txt = ""
see "["
for n = 1 to len(array)
txt = txt + array[n] + ","
next
txt = left(txt,len(txt)-1)
txt = txt + "]"
see txt
</lang>
Magnanimous numbers 1-45: [0,1,2,3,4,5,6,7,8,9,11,12,14,16,20,21,23,25,29,30,32,34,38,41,43,47,49,50,52,56,58,61,65,67,70,74,76,83,85,89,92,94,98,101,110] Magnanimous numbers 241-250: [17992,19972,20209,20261,20861,22061,22201,22801,22885,24407]
Ruby
<lang ruby>require "prime"
magnanimouses = Enumerator.new do |y|
(0..).each {|n| y << n if (1..n.digits.size-1).all? {|k| n.divmod(10**k).sum.prime?} }
end
puts "First 45 magnanimous numbers:" puts magnanimouses.first(45).join(' ')
puts "\n241st through 250th magnanimous numbers:" puts magnanimouses.first(250).last(10).join(' ')
puts "\n391st through 400th magnanimous numbers:" puts magnanimouses.first(400).last(10).join(' ') </lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Rust
<lang rust>fn is_prime(n: u32) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
if n % 3 == 0 {
return n == 3;
}
let mut p = 5;
while p * p <= n {
if n % p == 0 {
return false;
}
p += 2;
if n % p == 0 {
return false;
}
p += 4;
}
true
}
fn is_magnanimous(n: u32) -> bool {
let mut p: u32 = 10;
while n >= p {
if !is_prime(n % p + n / p) {
return false;
}
p *= 10;
}
true
}
fn main() {
let mut m = (0..).filter(|x| is_magnanimous(*x)).take(400);
println!("First 45 magnanimous numbers:");
for (i, n) in m.by_ref().take(45).enumerate() {
if i > 0 && i % 15 == 0 {
println!();
}
print!("{:3} ", n);
}
println!("\n\n241st through 250th magnanimous numbers:");
for n in m.by_ref().skip(195).take(10) {
print!("{} ", n);
}
println!("\n\n391st through 400th magnanimous numbers:");
for n in m.by_ref().skip(140) {
print!("{} ", n);
}
println!();
}</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Sidef
<lang ruby>func is_magnanimous(n) {
1..n.ilog10 -> all {|k|
sum(divmod(n, k.ipow10)).is_prime
}
}
say "First 45 magnanimous numbers:" say is_magnanimous.first(45).join(' ')
say "\n241st through 250th magnanimous numbers:" say is_magnanimous.first(250).last(10).join(' ')
say "\n391st through 400th magnanimous numbers:" say is_magnanimous.first(400).last(10).join(' ')</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Swift
<lang swift>import Foundation
func isPrime(_ n: Int) -> Bool {
if n < 2 {
return false
}
if n % 2 == 0 {
return n == 2
}
if n % 3 == 0 {
return n == 3
}
var p = 5
while p * p <= n {
if n % p == 0 {
return false
}
p += 2
if n % p == 0 {
return false
}
p += 4
}
return true
}
func isMagnanimous(_ n: Int) -> Bool {
var p = 10;
while n >= p {
if !isPrime(n % p + n / p) {
return false
}
p *= 10
}
return true
}
let m = (0...).lazy.filter{isMagnanimous($0)}.prefix(400); print("First 45 magnanimous numbers:"); for (i, n) in m.prefix(45).enumerated() {
if i > 0 && i % 15 == 0 {
print()
}
print(String(format: "%3d", n), terminator: " ")
} print("\n\n241st through 250th magnanimous numbers:"); for n in m.dropFirst(240).prefix(10) {
print(n, terminator: " ")
} print("\n\n391st through 400th magnanimous numbers:"); for n in m.dropFirst(390) {
print(n, terminator: " ")
} print()</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081
Visual Basic .NET
<lang vbnet>Imports System, System.Console
Module Module1
Dim np As Boolean()
Sub ms(ByVal lmt As Long)
np = New Boolean(CInt(lmt)) {} : np(0) = True : np(1) = True
Dim n As Integer = 2, j As Integer = 1 : While n < lmt
If Not np(n) Then
Dim k As Long = CLng(n) * n
While k < lmt : np(CInt(k)) = True : k += n : End While
End If : n += j : j = 2 : End While
End Sub
Function is_Mag(ByVal n As Integer) As Boolean
Dim res, rm As Integer, p As Integer = 10
While n >= p
res = Math.DivRem(n, p, rm)
If np(res + rm) Then Return False
p = p * 10 : End While : Return True
End Function
Sub Main(ByVal args As String())
ms(100_009) : Dim mn As String = " magnanimous numbers:"
WriteLine("First 45{0}", mn) : Dim l As Integer = 0, c As Integer = 0
While c < 400 : If is_Mag(l) Then
c += 1 : If c <= 45 OrElse (c > 240 AndAlso c <= 250) OrElse c > 390 Then Write(If(c <= 45, "{0,4} ", "{0,8:n0} "), l)
If c < 45 AndAlso c Mod 15 = 0 Then WriteLine()
If c = 240 Then WriteLine(vbLf & vbLf & "241st through 250th{0}", mn)
If c = 390 Then WriteLine(vbLf & vbLf & "391st through 400th{0}", mn)
End If : l += 1 : End While
End Sub
End Module</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17,992 19,972 20,209 20,261 20,861 22,061 22,201 22,801 22,885 24,407 391st through 400th magnanimous numbers: 486,685 488,489 515,116 533,176 551,558 559,952 595,592 595,598 600,881 602,081
Wren
<lang ecmascript>import "/fmt" for Conv, Fmt import "/math" for Int
var isMagnanimous = Fn.new { |n|
if (n < 10) return true
var p = 10
while (true) {
var q = (n/p).floor
var r = n % p
if (!Int.isPrime(q + r)) return false
if (q < 10) break
p = p * 10
}
return true
}
var listMags = Fn.new { |from, thru, digs, perLine|
if (from < 2) {
System.print("\nFirst %(thru) magnanimous numbers:")
} else {
System.print("\n%(Conv.ord(from)) through %(Conv.ord(thru)) magnanimous numbers:")
}
var i = 0
var c = 0
while (c < thru) {
if (isMagnanimous.call(i)) {
c = c + 1
if (c >= from) {
System.write(Fmt.d(digs, i) + " ")
if (c % perLine == 0) System.print()
}
}
i = i + 1
}
}
listMags.call(1, 45, 3, 15) listMags.call(241, 250, 1, 10) listMags.call(391, 400, 1, 10)</lang>
- Output:
First 45 magnanimous numbers: 0 1 2 3 4 5 6 7 8 9 11 12 14 16 20 21 23 25 29 30 32 34 38 41 43 47 49 50 52 56 58 61 65 67 70 74 76 83 85 89 92 94 98 101 110 241st through 250th magnanimous numbers: 17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 391st through 400th magnanimous numbers: 486685 488489 515116 533176 551558 559952 595592 595598 600881 602081