I'm looking for a tool (like Wolfram Alpha) that can calculate the result of $ B(P,N) $
Where $B(P,N)$ is a recursive function defined as follows:
$ \left\{\begin{matrix} B(P,N)=\frac{-(-1)^{\frac{N}{2^{P-1}}+\sum_{i=1}^{P-1}(\frac{-B(P-i,N)}{2^{i}})}+1}{2}\\ P\in \mathbb{N}_{>0}\\ N\in \mathbb{N} \end{matrix}\right. $
Note that $ \sum_{i=1}^{0}f(x)=0 $ summation is an empty sum, so:
$$ B(1,N)=\frac{-(-1)^{\frac{N}{2^{1-1}}+\sum_{i=1}^{0}(\frac{-B(0,N)}{2^{i}})}+1}{2}=\frac{-(-1)^{\frac{N}{2^{0}}+0}+1}{2}=\frac{-(-1)^{N}+1}{2} $$
I tried using Wolfram Alpha, but it didn't work.
$\endgroup$ 112 Answers
$\begingroup$I defined:$$ S(P,N) = \sum_{i=1}^P \frac{ B(P-i,N) }{2^i}$$And rewrote your equations as:$$B(P,N) = \frac{1 - (-1)_{}^{ \frac{N}{2^{P-1}} - S(P-1,N)}}{2}$$$$S(P,N) = \frac{B(P,N) + S(P-1,N)}{2}$$Then I implemented them in Python with the following code:
def B(P, N, memo_B=None, memo_S=None, verbose=False): if not (type(P) is int and type(N) is int): raise ValueError("P and N must be integers") if P < 1: raise ValueError("P must be at least 1") if memo_B == None: memo_B = {} if memo_S == None: memo_S = {(0,N): int(0)} if (P,N) in memo_B: return memo_B[(P,N)] if (P-1,N) in memo_S: sb = memo_S[(P-1,N)] else: sb = ( B(P-1, N, memo_B, memo_S, verbose=verbose) + S(P-2, N, memo_B, memo_S, verbose=verbose) ) if sb % 2 == 0: sb = int(sb//2) else: sb = sb/2 bb = (int(1) - (int(-1))**( N/(2**(P-1)) - sb)) if bb % 2 == 0: bb = int(bb//2) else: bb = bb/2 memo_S[(P-1,N)] = sb memo_B[(P,N)] = bb if verbose: print(f"S({P-1},{N}) = {sb}") print(f"B({P},{N}) = {bb}") return bb
def S(PS, NS, memo_B, memo_S, verbose=False): if (PS, NS) in memo_S: return memo_S[(PS, NS)] else: if (PS, NS) in memo_B: bs = memo_B[(PS, NS)] else: bs = B(PS, NS, memo_B, memo_S, verbose=verbose) if (PS-1, NS) in memo_S: ss = memo_S[(PS-1, NS)] else: ss = S(PS-1, NS, memo_B, memo_S, verbose=verbose) memo_S[(PS-1,NS)] = ss memo_B[(PS,NS)] = bs if verbose: print(f"S({PS-1},{NS}) = {ss}") print(f"S({PS},{NS}) = {bs}") return ssWhen I tested it with this:
for j in range(11): bits = [None]*4 for i in range(4): bits[3-i] = B(i+1,j) print(bits)The output was as expected:
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]Thanks for your help @Joe.
I also found another solution using Wolfram Language ()
b[p_Integer,n_Integer]:=(-Power[-1,n/Power[2,p-1]+Sum[-b[p-i,n]/Power[2,i],{i,1,p-1}]]+1)/2
B[l_Integer,n_Integer]:=Sum[b[j,n]*Power[10,j-1],{j,1,l}]
B[8,121]Output:
1111101
