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.

Pages: 1 2

5 Responses to “K-Factorials And Factorions”

  1. Rutger said

    “The Loneliness of the Factorions”

    def factorial(n, k):
    	result = 1
    	n_mod_k = n % k
    	for i in range(2, n+1):
    		if i % k == n_mod_k:
    			result *= i
    	return result
    
    
    def is_factorion(n, k):
    	try:
    		return n == sum(factorial(int(i), k) for i in list(str(n)))
    	except:
    		return -1
    
    
    
    for k in range(1, 11):
    	for i in range(1000000):
    		if is_factorion(i, k):
    			print "%i-factorion:"%k, i
    
    # output:
    # 1-factorion: 1
    # 1-factorion: 2
    # 1-factorion: 145
    # 1-factorion: 40585
    # 2-factorion: 1
    # 2-factorion: 2
    # 2-factorion: 3
    # 2-factorion: 107
    # 3-factorion: 1
    # 3-factorion: 2
    # 3-factorion: 3
    # 3-factorion: 4
    # 3-factorion: 81
    # 3-factorion: 82
    # 3-factorion: 83
    # 3-factorion: 84
    # 4-factorion: 1
    # 4-factorion: 2
    # 4-factorion: 3
    # 4-factorion: 4
    # 4-factorion: 5
    # 4-factorion: 49
    # 5-factorion: 1
    # 5-factorion: 2
    # 5-factorion: 3
    # 5-factorion: 4
    # 5-factorion: 5
    # 5-factorion: 6
    # 5-factorion: 39
    # 6-factorion: 1
    # 6-factorion: 2
    # 6-factorion: 3
    # 6-factorion: 4
    # 6-factorion: 5
    # 6-factorion: 6
    # 6-factorion: 7
    # 6-factorion: 29
    # 7-factorion: 1
    # 7-factorion: 2
    # 7-factorion: 3
    # 7-factorion: 4
    # 7-factorion: 5
    # 7-factorion: 6
    # 7-factorion: 7
    # 7-factorion: 8
    # 7-factorion: 19
    # 8-factorion: 1
    # 8-factorion: 2
    # 8-factorion: 3
    # 8-factorion: 4
    # 8-factorion: 5
    # 8-factorion: 6
    # 8-factorion: 7
    # 8-factorion: 8
    # 8-factorion: 9
    # 9-factorion: 1
    # 9-factorion: 2
    # 9-factorion: 3
    # 9-factorion: 4
    # 9-factorion: 5
    # 9-factorion: 6
    # 9-factorion: 7
    # 9-factorion: 8
    # 9-factorion: 9
    # 10-factorion: 1
    # 10-factorion: 2
    # 10-factorion: 3
    # 10-factorion: 4
    # 10-factorion: 5
    # 10-factorion: 6
    # 10-factorion: 7
    # 10-factorion: 8
    # 10-factorion: 9
    # [Finished in 108.7s]
    
  2. Rutger said

    whops..

    line 14: return False

  3. Andras said

    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)

    }

  4. Andras said

    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)
    
    }
    
  5. bitchef said

    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: