Magnanimous numbers: Difference between revisions
Content added Content deleted
| Line 851: | Line 851: | ||
434 |
434 |
||
strange=: ({. + [: i. -~/)@:(_1 0&+) |
strange=: ({. + [: i. -~/)@:(_1 0&+) NB. produce index ranges for output |
||
I=: _2 <@strange\ 1 45 241 250 391 400 |
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 |
|||
| ⚫ | |||
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤ |
|||
│17992 19972 20209 20261 20861 22061 22201 22801 22885 24407 │ |
|||
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤ |
|||
| ⚫ | |||
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘ |
|||
</pre> |
</pre> |
||
Revision as of 14:25, 17 March 2021
Magnanimous numbers 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.
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 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
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]
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
<lang Phix>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]})</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}
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 genP subroutine could use a lot of optimization if wanted.
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.*/
#= 0; $= /*#: magnanimous # cnt; $: is a list*/
do k=0 until #==HI /* [↓] traipse through the number(s). */
if \magna(k) then iterate /*Not magnanimous? Then skip this num.*/
#= # + 1 /*bump the magnanimous number count. */
if #>=LO then $= $ k /*In range► Then add number ──► $ list*/
end /*k*/
say
say center(' 'LO "──►" HI 'magnanimous numbers ', 126, "─")
say strip($)
end /*j*/
exit /*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; nP=6 /*assign low primes; # primes.*/
!.= 0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1 /*assign primality to numbers.*/
do j=@.nP+4 by 2 to highP /*only find odd primes from here on. */
parse var j -1 _;if _==5 then iterate /*Is last digit a "5"? Then not prime*/
if j// 3==0 then iterate /*is J divisible by 3? " " " */
if j// 7==0 then iterate /* " " " " 7? " " " */
if j//11==0 then iterate /* " " " " 11? " " " */
if j//13==0 then iterate /* " " " " 13? " " " */
do k=7 while k*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. */
nP= nP+1; !.j= 1; @.nP= j /*bump P cnt; assign P to @. and !. */
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