Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

August 2022 - Solution

<< July September >>

August 2022 Challenge

August 2022 Solution:

The numerical solutions are

2524614399 for 2^24
920321499 for 2^256

The sequence s(n) for the number of ways to perform an n-time dance satisfies a recurrence relation, which can be systematically obtained by constructing a state transition diagram and computing the recurrence relation from its reprenting matrix using standard combinatorial techniques. To compute the recurrence relation for large numbers in general can be done using Fiduccia's algorithm see but here since n is a power of 2, it can be done using iterative squaring.