How to calculate the result of a recursive equation?

Question

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.

Answer 1

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 ss

When 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]

Answer 2

Thanks for your help @Joe.

I also found another solution using Wolfram Language (https://community.wolfram.com/groups/-/m/t/2354584)

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