Divisor tree / Consecutive dealing in heaps

Hmm, I have found some inconsistences in this program. Not good. Investigating further...

This program shows the different (unique) ways of "consecutive dealing" N things into separate heaps with the same number of things in each heap. The method for this consecutive dealing is:

start with one heap of N things
deal these N things into separate heaps so all heaps has the same number of things
take one of these heaps and continue to deal in the same way, until there is just one thing in each heap.

There is a simple method of calculating the different number of ways of this consecutive dealing. Here is the pseudo code for the method:


divtree(n):

   if      n == 1           then value = 1  # special case for n == 1

    elsif   prime(n)         then value = 1  # n is a prime number

    else if prime_square(n)  then value = 1  # n is square of a prime

    else if

       for div = divisors(n) do                # else: loop through the divisors of n

           next if div == 1 or div == n          # except for 1 and n itself

         value = value + divtree(div)   # sum the values of the divisors, recursively 



    return value

Please note that for large values the page can be quite large and the web browser may take some time to parse the page.

This program was described in the (swedish) blog post Divisorträd: unika sätt att göra konsekutiva uppdelningar.

Divisor tree

Result

24 is a prime: no
Factors: 2 2 2 3
Divisors: 1 2 3 4 6 8 12 24

Ways of dealing the heaps consecutively:
24 / 2 heaps = 12 things in each heap (2 -> 12 -> ..)
     12 / 2 heaps = 6 things in each heap (2 -> 6 -> ..)
         6 / 2 heaps = 3 things in each heap (2 -> 3)
         6 / 3 heaps = 2 things in each heap (3 -> 2)
     12 / 3 heaps = 4 things in each heap (3 -> 4 -> ..)
         4 / 2 heaps = 2 things in each heap (2 -> 2)
     12 / 4 heaps = 3 things in each heap (4 -> 3)
     12 / 6 heaps = 2 things in each heap (6 -> 2)
24 / 3 heaps = 8 things in each heap (3 -> 8 -> ..)
     8 / 2 heaps = 4 things in each heap (2 -> 4 -> ..)
         4 / 2 heaps = 2 things in each heap (2 -> 2)
     8 / 4 heaps = 2 things in each heap (4 -> 2)
24 / 4 heaps = 6 things in each heap (4 -> 6 -> ..)
     6 / 2 heaps = 3 things in each heap (2 -> 3)
     6 / 3 heaps = 2 things in each heap (3 -> 2)
24 / 6 heaps = 4 things in each heap (6 -> 4 -> ..)
     4 / 2 heaps = 2 things in each heap (2 -> 2)
24 / 8 heaps = 3 things in each heap (8 -> 3)
24 / 12 heaps = 2 things in each heap (12 -> 2)

Found 12 ways for N = 24.

Checking: adding values for the divisors, except for 1 and 24:

2: 1
3: 1
4: 1
6: 2
8: 2
12: 5

Addition of values for the divisors: 2 + 3 + 4 + 6 + 8 + 12 = 12

Sequence
Number of ways of consecutive dealing n objects for n = 1 .. 24:
1 1 1 1 1 2 1 2 1 2 1 5 1 2 2 4 1 5 1 5 2 2 1 12

My other "useless" programs
Back to my homepage
Created by Hakan Kjellerstrand hakank@bonetmail.com