K-Factorials And Factorions
August 18, 2015
We begin with a function that determines whether an input number n is a k-factorion to base b:
(define (factorion? n k b)
(let ((ks (make-vector 10 1)))
(do ((d 2 (+ d 1))) ((= d 10))
(do ((i 1 (+ i 1))) ((< d i))
(if (= (modulo d k) (modulo i k))
(vector-set! ks d (* i (vector-ref ks d))))))
(let loop ((ds (digits n b)) (f 0))
(if (null? ds) (= f n)
(loop (cdr ds) (+ f (vector-ref ks (car ds))))))))
> (factorion? 145 1 10) #t > (factorion? 81 3 10) #t
Here, ks is a vector of the k-factorials of the digits less than the base b. Instead of testing a single factorion this function computes a list of factorions:
(define (factorions k b)
(let ((ks (make-vector b 1)))
(do ((d 2 (+ d 1))) ((= d b))
(do ((i 1 (+ i 1))) ((< d i))
(when (= (modulo d k) (modulo i k))
(vector-set! ks d (* i (vector-ref ks d))))))
(do ((n 1 (+ n 1))) (#f)
(when (= n (sum (map (lambda (d) (vector-ref ks d)) (digits n b))))
(display n) (newline)))))
> (factorions 1 10) 1 2 145 40585 CTRL-C > (factorions 1 6) 1 2 25 26 CTRL-C
We could improve that by noting that the factorion of an n-digit number cannot exceed n * (b-1)!.
We used the digits function from the Standard Prelude. You can run the program at http://ideone.com/gL8Nl3.
If you’re interested in k-factorials and factorions, you might look at oeis.org, where searches for such topics as “factorions” and “double factorials” can lead to an evening of quiet contemplation. John Cook has a blog entry where he shows a fascinating use of double factorials.
“The Loneliness of the Factorions”
whops..
line 14: return False
Scala:
package programmingpraxis
//https://programmingpraxis.com/2015/08/18/k-factorials-and-factorions/
object KFactorial {
def kFactorial(n: Int, k: Int=1): Int = 1 to n filter (_ % k == n % k) product
//> kFactorial: (n: Int, k: Int)Int
def isKFactorion(n: Int, k: Int=1): Boolean = n == n.toString.map(x => kFactorial(x.toString.toInt, k)).sum
//> isKFactorion: (n: Int, k: Int)Boolean
(for(k res0: String = 1factorions: Vector(1, 2, 145, 40585)
//| 2factorions: Vector(1, 2, 3, 107)
//| 3factorions: Vector(1, 2, 3, 4, 81, 82, 83, 84)
//| 4factorions: Vector(1, 2, 3, 4, 5, 49)
//| 5factorions: Vector(1, 2, 3, 4, 5, 6, 39)
//| 6factorions: Vector(1, 2, 3, 4, 5, 6, 7, 29)
//| 7factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 19)
//| 8factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 9)
//| 9factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 9)
//| 10factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 9)
}
Test Formatting Scala with scala:
package programmingpraxis //https://programmingpraxis.com/2015/08/18/k-factorials-and-factorions/ object KFactorial { def kFactorial(n: Int, k: Int=1): Int = 1 to n filter (_ % k == n % k) product //> kFactorial: (n: Int, k: Int)Int def isKFactorion(n: Int, k: Int=1): Boolean = n == n.toString.map(x => kFactorial(x.toString.toInt, k)).sum //> isKFactorion: (n: Int, k: Int)Boolean (for(k<-1 to 10) yield k+"factorions: "+ (1 to 100000 filter(isKFactorion(_, k)))) mkString("\r\n") //> res0: String = 1factorions: Vector(1, 2, 145, 40585) //| 2factorions: Vector(1, 2, 3, 107) //| 3factorions: Vector(1, 2, 3, 4, 81, 82, 83, 84) //| 4factorions: Vector(1, 2, 3, 4, 5, 49) //| 5factorions: Vector(1, 2, 3, 4, 5, 6, 39) //| 6factorions: Vector(1, 2, 3, 4, 5, 6, 7, 29) //| 7factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 19) //| 8factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 9) //| 9factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 9) //| 10factorions: Vector(1, 2, 3, 4, 5, 6, 7, 8, 9) }Interesting topic.
Is there a direct way to determine if a number is factorion?
To get the k-factorials, I just implemented the mathematical definition as is in Python as:
def k_factorial(n,k): if n <= 0: return 1 elif n < k: return n else: return n * k_factorial(n-k,k)And I checked for the kth factorions with:
def is_factorion(n, k): return sum(k_factorial(int(i),k) for i in list(str(n))) == int(n)