Last active
August 15, 2023 13:29
-
-
Save shmalex/34acb9b1af72f41174c0c8192983c429 to your computer and use it in GitHub Desktop.
Sum of Ones in Matrix 2^n by 2^(n+1)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import numpy as np | |
def sum_of_bins_greater_then(n): | |
print("n =",n) | |
left = [] | |
for i in range(2**n): | |
left += [sum(int(x) for x in bin(i)[2:])] | |
up = [] | |
for i in range(2**(n+1)): | |
up += [sum(int(x) for x in bin(i)[2:])] | |
print("Matrix shape", len(left),'x',len(up)) | |
m = np.zeros((2**n, 2**(n+1)))-1 | |
for li, l in enumerate(left): | |
# print('') | |
for ui, u in enumerate(up): | |
m[li,ui]=int(l<u) | |
# print(f"{0:1}", int(m[li,ui]), end=' ') | |
twopowertwoN = 2**(2*n) | |
print('2^(2*n)=', twopowertwoN) | |
print('Matrix sum', int(np.sum(m))) | |
print("Equals?",twopowertwoN==np.sum(m)) | |
print('') | |
# Main Run ~5 minutes | |
for i in range(15): | |
sum_of_bins_greater_then(i) | |
""" | |
OUTPUT | |
n = 0 | |
Matrix shape 1 x 2 | |
2^(2*n)= 1 | |
Matrix sum 1 | |
Equals? True | |
n = 1 | |
Matrix shape 2 x 4 | |
2^(2*n)= 4 | |
Matrix sum 4 | |
Equals? True | |
n = 2 | |
Matrix shape 4 x 8 | |
2^(2*n)= 16 | |
Matrix sum 16 | |
Equals? True | |
n = 3 | |
Matrix shape 8 x 16 | |
2^(2*n)= 64 | |
Matrix sum 64 | |
Equals? True | |
n = 4 | |
Matrix shape 16 x 32 | |
2^(2*n)= 256 | |
Matrix sum 256 | |
Equals? True | |
n = 5 | |
Matrix shape 32 x 64 | |
2^(2*n)= 1024 | |
Matrix sum 1024 | |
Equals? True | |
n = 6 | |
Matrix shape 64 x 128 | |
2^(2*n)= 4096 | |
Matrix sum 4096 | |
Equals? True | |
n = 7 | |
Matrix shape 128 x 256 | |
2^(2*n)= 16384 | |
Matrix sum 16384 | |
Equals? True | |
n = 8 | |
Matrix shape 256 x 512 | |
2^(2*n)= 65536 | |
Matrix sum 65536 | |
Equals? True | |
n = 9 | |
Matrix shape 512 x 1024 | |
2^(2*n)= 262144 | |
Matrix sum 262144 | |
Equals? True | |
n = 10 | |
Matrix shape 1024 x 2048 | |
2^(2*n)= 1048576 | |
Matrix sum 1048576 | |
Equals? True | |
n = 11 | |
Matrix shape 2048 x 4096 | |
2^(2*n)= 4194304 | |
Matrix sum 4194304 | |
Equals? True | |
n = 12 | |
Matrix shape 4096 x 8192 | |
2^(2*n)= 16777216 | |
Matrix sum 16777216 | |
Equals? True | |
n = 13 | |
Matrix shape 8192 x 16384 | |
2^(2*n)= 67108864 | |
Matrix sum 67108864 | |
Equals? True | |
n = 14 | |
Matrix shape 16384 x 32768 | |
2^(2*n)= 268435456 | |
Matrix sum 268435456 | |
Equals? True | |
""" | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment