Magnanimous numbers
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
Factor
<lang factor>USING: arrays grouping io kernel lists lists.lazy lists.lazy.examples math math.parser math.primes math.ranges prettyprint sequences ;
! Optimization for numbers > 1001; ! first and last digits must have opposite parity. ! Thanks to Raku entry for this.
- mixed-parity? ( str -- ? )
[ first even? ] [ last even? xor ] bi ;
- >stringy ( l -- l ) [ number>string ] lmap-lazy ;
- 1001- ( -- l ) naturals [ 1002 < ] lwhile >stringy ;
- 1002+ ( -- l ) 1002 lfrom >stringy [ mixed-parity? ] lfilter ;
- candidates ( -- l ) 1001- 1002+ lappend-lazy ;
- (magnanimous?) ( str -- ? )
dup length 1 - [1,b] [ cut 2array ] with map [ [ string>number ] map-sum ] map [ prime? ] all? ;
- magnanimous? ( str -- ? )
dup length 1 = [ drop t ] [ (magnanimous?) ] if ;
- magnanimous ( -- l ) candidates [ magnanimous? ] lfilter ;
- show ( seq from to -- ) rot subseq 15 group simple-table. nl ;
400 magnanimous ltake list>array [ "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
Raku
<lang perl6>my @magnanimous = lazy flat ^10, (10 .. 1001).hyper.map( {
my $last;
(1 .. .chars - 1).map: -> \c { ++$last and last unless (.substr(0,c) + .substr(c)).is-prime }
next if $last;
$_
} ),
(1002 .. ∞).hyper.map: {
# optimization for numbers > 1001; First and last digit can not both be even or both be odd
next if (.substr(0,1) % 2 + .substr(*-1) % 2) %% 2;
my $last;
(1 .. .chars - 1).map: -> \c { ++$last 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 generated a list (sparse array) of suitable primes.
The genP subroutine could use a lot of optimization if wanted.
The magna function was quite simple to code and pretty fast.
<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 /* [↑] traispe 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 /*obtain the number to be examined. */
if x<10 then return 1 /*single digit numbers are magnanimous.*/
do s= 1 to length(x)-1 /*traipse thr number, inserting + sign.*/
parse var x y +(s) z; sum= y + z /*parse 2 parts of #, sum 'em*/
if !.sum then iterate /*Sum is a prime? Then 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 lim=nP until lim>=highP; end /*only keep primes up to the sqrt(HI). */
do j=@.nP+4 by 2 to highP /*only find odd primes from here on. */
if j// 3==0 then iterate /*is J divisible by #3 Then not prime*/
parse var j -1 _;if _==5 then iterate /*Is last digit a "5"? " " " */
if j// 7==0 then iterate /*is J divisible by 7? " " " */
if j//11==0 then iterate /* " " " " 11? " " " */
if j//13==0 then iterate /*is " " " 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; @.nP= j; !.j= 1 /*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