20220903, 11:47  #12  
Oct 2017
2·5·13 Posts 
Quote:
0,072 seconds for the transition from 2^n to 2^(n+1) Last fiddled with by Dieter on 20220903 at 11:49 

20220905, 17:50  #13  
Jul 2015
2×7 Posts 
Quote:
Code:
D = 3141592653 # dance arrangement can be classified into 7 cases # by [1 / 11 / 12 / 13 / 22 / 23 / 33] # which means # one dancer with 1 unit of time # two dancer with 1,1 units of time # two dancer with 1,2 units of time # two dancer with 1,3 units of time # two dancer with 2,2 units of time # two dancer with 2,3 units of time # two dancer with 3,3 units of time # from a case to another case, # the number of possible arrangement can constitute a matrix ori_M = [[3, 2, 2, 2, 2, 2, 2], [6, 0, 0, 0, 0, 0, 0], [0, 4, 2, 2, 0, 0, 0], [0, 0, 2, 0, 4, 2, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0]] def count(N): ori_N = N N = N  1 # number to binary N_binary = [] while N > 0: if N % 2 == 0: N_binary.append(0) else: N_binary.append(1) N = N // 2 # initial matrix if len(N_binary) == 0: M = [[1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1]] else: M = [[3, 2, 2, 2, 2, 2, 2], [6, 0, 0, 0, 0, 0, 0], [0, 4, 2, 2, 0, 0, 0], [0, 0, 2, 0, 4, 2, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0]] # calculate M^N for i in range(len(N_binary)2, 1, 1): next_M = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]] for j in range(7): for k in range(7): for l in range(7): next_M[j][k] += M[j][l] * M[l][k] for j in range(7): for k in range(7): M[j][k] = next_M[j][k] % D if N_binary[i] == 1: next_M = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]] for j in range(7): for k in range(7): for l in range(7): next_M[j][k] += M[j][l] * ori_M[l][k] for j in range(7): for k in range(7): M[j][k] = next_M[j][k] % D # number of arrangement = M^N * A A = [4, 12, 0, 0, 0, 0, 0] next_A = [0, 0, 0, 0, 0, 0, 0] for i in range(7): for j in range(7): next_A[i] += A[j] * M[i][j] for i in range(7): next_A[i] = next_A[i] % D # sum of all cases S = 0 for i in range(7): S += next_A[i] print(S % D) count(2**24) count(2**256) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
August 2021  tgan  Puzzles  3  20210906 11:24 
August 2020  Xyzzy  Puzzles  3  20200829 08:33 
August 2019  Xyzzy  Puzzles  20  20190909 09:40 
August 2014  Xyzzy  Puzzles  2  20141102 19:04 
August Progress  Wacky  NFSNET Discussion  0  20070809 02:32 