Factorions
From Rosetta Code
Factorions 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.
- Definition
A factorion is a natural number that equals the sum of the factorials of its digits.
- Example
145 is a factorion in base 10 because:
1! + 4! + 5! = 1 + 24 + 120 = 145
It can be shown (see the Wikipedia article below) that no factorion in base 10 can exceed 1,499,999.
- Task
Write a program in your language to demonstrate, by calculating and printing out the factorions, that shows:
- There are 3 factorions in base 9
- There are 4 factorions in base 10
- There are 5 factorions in base 11
- There are 2 factorions in base 12 (up to the same upper bound as for base 10)
ALGOL 68[edit]
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
- 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[edit]
#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;
}
- 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[edit]
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
- 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
Fōrmulæ[edit]
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
Go[edit]
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")
}
}
- 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
Julia[edit]
isfactorian(n, base) = mapreduce(factorial, +, map(c -> parse(Int, c, base=16), split(string(n, base=base), ""))) == n
printallfactorian(base) = println("Factorians for base $base: ", [n for n in 1:100000 if isfactorian(n, base)])
foreach(printallfactorian, 9:12)
- Output:
Factorians for base 9: [1, 2, 41282] Factorians for base 10: [1, 2, 145, 40585] Factorians for base 11: [1, 2, 26, 48, 40472] Factorians for base 12: [1, 2]
OCaml[edit]
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
Perl 6[edit]
constant @factorial = 1, |[\*] 1..*;
constant $limit = 1500000;
constant $bases = 9 .. 12;
my @result;
$bases.race(:1batch).map: -> $base {
@result[$base] = "\nFactorions in base $base:\n1 2";
sink (1 .. $limit div $base).map: -> $i {
my $product = $i * $base;
my $partial;
for $i.polymod($base xx *) {
$partial += @factorial[$_];
last if $partial > $product
}
next if $partial > $product;
my $sum;
for ^$base {
last if ($sum = $partial + @factorial[$_]) > $product + $_;
@result[$base] ~= " $sum" and last if $sum == $product + $_
}
}
}
.say for @result[$bases];
- 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[edit]
/*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.*/
- 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[edit]
var facts=[0..12].pump(List,fcn(n){ (1).reduce(n,fcn(N,n){ N*n },1) }); #(1,1,2,6....)
fcn factorions(base){
fs:=List();
foreach n in ([1..1_499_999]){
sum,j := 0,n;
while(j){
sum+=facts[j%base];
j/=base;
}
if(sum==n) fs.append(n);
}
fs
}
foreach n in ([9..12]){
println("The factorions for base %2d are: ".fmt(n),factorions(n).concat(" "));
}
- 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
