Factorions: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Minor tweaks , better concurrency) |
m (→{{header|REXX}}: cut back (one) on the (limit) of calculations of the factorials) |
||
Line 260: | Line 260: | ||
if lim=='' | lim=="," then lim= 1500000 - 1 /* " " " " " " */ |
if lim=='' | lim=="," then lim= 1500000 - 1 /* " " " " " " */ |
||
do fact=0 |
do fact=0 for HIb; !.fact= !(fact) /*use memoization for factorials. */ |
||
end /*fact*/ |
end /*fact*/ |
||
Revision as of 21:56, 12 August 2019
- Definition
A factorion is a natural number that equals the sum of the factorials of its digits. For example 145 is a factorion in base 10 because:
1! + 4! + 5! = 1 + 24 + 120 = 145.
- Task
It can be shown (see Wikipedia article below) that no factorion in base 10 can exceed 1,499,999.
Write a program in your language to demonstrate, by calculating and printing out the factorions, that:
1. There are 4 factorions in base 10.
2. There are 3 factorions in base 9, 5 factorions in base 11 but only 2 factorions in base 12 up to the same upper bound as for base 10.
- See also
ALGOL 68
<lang algol68>BEGIN
# cache factorials from 0 to 11 # [ 0 : 11 ]INT fact; fact[0] := 1; FOR n TO 11 DO fact[n] := fact[n-1] * n OD; FOR b FROM 9 TO 12 DO print( ( "The factorions for base ", whole( b, 0 ), " are:", newline ) ); FOR i TO 1500000 - 1 DO INT sum := 0; INT j := i; WHILE j > 0 DO sum +:= fact[ j MOD b ]; j OVERAB b OD; IF sum = i THEN print( ( whole( i, 0 ), " " ) ) FI OD; print( ( newline ) ) OD
END</lang>
- Output:
The factorions for base 9 are: 1 2 41282 The factorions for base 10 are: 1 2 145 40585 The factorions for base 11 are: 1 2 26 48 40472 The factorions for base 12 are: 1 2
C
<lang c>#include <stdio.h>
int main() {
int n, b, d; unsigned long long i, j, sum, fact[12]; // cache factorials from 0 to 11 fact[0] = 1; for (n = 1; n < 12; ++n) { fact[n] = fact[n-1] * n; }
for (b = 9; b <= 12; ++b) { printf("The factorions for base %d are:\n", b); for (i = 1; i < 1500000; ++i) { sum = 0; j = i; while (j > 0) { d = j % b; sum += fact[d]; j /= b; } if (sum == i) printf("%llu ", i); } printf("\n\n"); } return 0;
}</lang>
- Output:
The factorions for base 9 are: 1 2 41282 The factorions for base 10 are: 1 2 145 40585 The factorions for base 11 are: 1 2 26 48 40472 The factorions for base 12 are: 1 2
Factor
<lang factor>USING: formatting io kernel math math.parser math.ranges memoize prettyprint sequences ; IN: rosetta-code.factorions
! Memoize factorial function MEMO: factorial ( n -- n! ) [ 1 ] [ [1,b] product ] if-zero ;
- factorion? ( n base -- ? )
dupd >base string>digits [ factorial ] map-sum = ;
- show-factorions ( limit base -- )
dup "The factorions for base %d are:\n" printf [ [1,b) ] dip [ dupd factorion? [ pprint bl ] [ drop ] if ] curry each nl ;
1,500,000 9 12 [a,b] [ show-factorions nl ] with each</lang>
- Output:
The factorions for base 9 are: 1 2 41282 The factorions for base 10 are: 1 2 145 40585 The factorions for base 11 are: 1 2 26 48 40472 The factorions for base 12 are: 1 2
Go
<lang go>package main
import (
"fmt" "strconv"
)
func main() {
// cache factorials from 0 to 11 var fact [12]uint64 fact[0] = 1 for n := uint64(1); n < 12; n++ { fact[n] = fact[n-1] * n }
for b := 9; b <= 12; b++ { fmt.Printf("The factorions for base %d are:\n", b) for i := uint64(1); i < 1500000; i++ { digits := strconv.FormatUint(i, b) sum := uint64(0) for _, digit := range digits { if digit < 'a' { sum += fact[digit-'0'] } else { sum += fact[digit+10-'a'] } } if sum == i { fmt.Printf("%d ", i) } } fmt.Println("\n") }
}</lang>
- Output:
The factorions for base 9 are: 1 2 41282 The factorions for base 10 are: 1 2 145 40585 The factorions for base 11 are: 1 2 26 48 40472 The factorions for base 12 are: 1 2
OCaml
<lang ocaml>let () =
(* cache factorials from 0 to 11 *) let fact = Array.make 12 0 in fact.(0) <- 1; for n = 1 to pred 12 do fact.(n) <- fact.(n-1) * n; done;
for b = 9 to 12 do Printf.printf "The factorions for base %d are:\n" b; for i = 1 to pred 1_500_000 do let sum = ref 0 in let j = ref i in while !j > 0 do let d = !j mod b in sum := !sum + fact.(d); j := !j / b; done; if !sum = i then (print_int i; print_string " ") done; print_string "\n\n"; done</lang>
Perl 6
<lang perl6>constant @f = 1, |[\*] 1..*;
constant $limit = 1500000;
for 9 .. 12 -> $b {
say "\n\nFactorions in base $b:";
print "$_ " if $_ == @f[$_] for ^$b;
(1 .. $limit div $b).hyper(:8degree).map: -> $i { my $sum; my $prod = $i * $b;
for $i.polymod($b xx *) { $sum += @f[$_]; $sum = 0 and last if $sum > $prod }
next if $sum == 0;
print "{$prod + $_} " and last if $sum + @f[$_] == $prod + $_ for ^$b; }
}</lang>
- Output:
Factorions in base 9: 1 2 41282 Factorions in base 10: 1 2 145 40585 Factorions in base 11: 1 2 26 48 40472 Factorions in base 12: 1 2
REXX
<lang rexx>/*REXX program calculates and displays factorions in bases nine ───► twelve. */ parse arg LOb HIb lim . /*obtain optional arguments from the CL*/ if LOb== | LOb=="," then LOb= 9 /*Not specified? Then use the default.*/ if HIb== | HIb=="," then HIb= 12 /* " " " " " " */ if lim== | lim=="," then lim= 1500000 - 1 /* " " " " " " */
do fact=0 for HIb; !.fact= !(fact) /*use memoization for factorials. */ end /*fact*/
do base=LOb to HIb /*process all the required bases. */ @= 1 2 /*initialize the list (@) to null. */ do j=3 for lim-2; $= 0 /*initialize the sum ($) to zero. */ t= j /*define the target (for the sum !'s).*/ do until t==0; d= t // base /*obtain a "digit".*/ $= $ + !.d /*add !(d) to sum.*/ t= t % base /*get a new target.*/ end /*until*/ if $==j then @= @ j /*Good factorial sum? Then add to list.*/ end /*i*/ say say 'The factorions for base ' base " are: " @ end /*base*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ !: procedure; arg x; !=1; do j=2 to x; !=!*j; end; return ! /*calc factorials.*/</lang>
- output when using the default inputs:
The factorions for base 9 are: 1 2 41282 The factorions for base 10 are: 1 2 145 40585 The factorions for base 11 are: 1 2 26 48 40472 The factorions for base 12 are: 1 2
zkl
<lang zkl>var facts=[0..12].pump(List,fcn(n){ (1).reduce(n,fcn(N,n){ N*n },1) }); #(1,1,2,6....) fcn factorions(base){
foreach n in ([1..1_499_999]){ sum,j := 0,n; while(j>0){
sum+=facts[j%base]; j/=base;
} if(sum==n) print(" ",n) } println();
}</lang> <lang zkl>foreach n in ([9..12]){
print("The factorions for base %2d are: ".fmt(n)); factorions(n);
}</lang>
- Output:
The factorions for base 9 are: 1 2 41282 The factorions for base 10 are: 1 2 145 40585 The factorions for base 11 are: 1 2 26 48 40472 The factorions for base 12 are: 1 2