128 or 96 bit integer types?

mensanator at aol.com mensanator at aol.com
Sun Jul 29 20:59:07 CEST 2007


On Jul 28, 3:34 am, David H Wild <dhw... at talktalk.net> wrote:
> In article <1185607142.096574.209... at e16g2000pri.googlegroups.com>,
>    mensana... at aol.com <mensana... at aol.com> wrote:
>
> > For example, how many ways can you put 492 marbles into
> > 264 ordered bins such that each bin has at least 1 marble?
> > The answer
> > 66189415264331559482776409694993032407028709677550
> > 59629130019289014193777349831417543311612293951363
> > 4124491233746912456893016976209252459301489030
> > has 146 digits.
>
> What on  earth made you think of that question?

Reearch on the Collatz Conjecture. Any Collatz
sequence can be described by a non-empty list of
integers > 0. Such as

[1,1,1,1,1,1,1,1]
[1,2,3,4,5,6]
[1009873,74396597698765,2,240895734075]

I proved that ANY posible list must exist on the
Collatz graph infinitely many times. The polynomials
derived from such a list identify the first occurence
of the set of infinite solutions.

For a sequence in 3n+C to be a loop cycle, it is
necessary (but not sufficient) for a power of 2
(2**p) to be congruent to a power of 3 (3**q) modulo
a divisor of C.

For example, the congruence classes of 2**p mod 41 are

(1,2,4,5,8,9,10,16,18,20,21,23,25,31,32,33,36,37,39,40)

the congruence classes of 3**q mod 41 are
(1,3,9,14,27,32,38,40)

The only classes they have in common are: {1,9,32,40}
so from this table,

p or q   2p (mod 41)   3q (mod 41)

0             1             1
1             2             3
2             4             9
3             8            27
4            16            40
5            32            38
6            23            32
7             5            14
8            10             1
9            20             3
10           40             9
11           39            27
12           37            40
13           33            38
14           25            32
15            9            14
16           18             1
17           36             3
18           31             9
19           21            27
20            1            40

only those p,q pairs (such as p=20 q=8) that have
matching congruence classes mod 41 can be potential
loop cycles in 3n+41.

This can be translated to the marble problem by asking
how many ways are there to make a list of q non-zero
positive integers that sum to p?

Of the 50388 ways, 8 of them have integer solutions
and because these 8 are cyclic permutaions, they
represent the same loop cycle

     [2,1,3,1,2,1,1,9] 1
     [1,3,1,2,1,1,9,2] 11
     [3,1,2,1,1,9,2,1] 37
     [1,2,1,1,9,2,1,3] 19
     [2,1,1,9,2,1,3,1] 49
     [1,1,9,2,1,3,1,2] 47
     [1,9,2,1,3,1,2,1] 91
     [9,2,1,3,1,2,1,1] 157

To actually answer you question, there is a known loop
cycle in 3n+85085 for which p=492 and q=264. If there is
one solution, there must be at leats 263 others (the
cyclic permutations), but to brute force search for any
others would require enumerating the answer to how many
ways can 492 marbles be put in 264 bins such that each
bin has at least 1 marble.

>
> --
> David Wild using RISC OS on broadbandwww.davidhwild.me.uk





More information about the Python-list mailing list