A379740 Number of calls to Karatsuba's multiplication algorithm K(x,y) when recursively calculating K(Fibonacci(n),Fibonacci(n+1)) in decimal digits.

1, 1, 1, 1, 1, 1, 4, 4, 4, 7, 7, 10, 10, 10, 10, 16, 22, 19, 19, 25, 25, 25, 31, 31, 22, 34, 34, 34, 34, 25, 43, 40, 40, 55, 37, 43, 55, 61, 61, 64, 67, 79, 79, 64, 70, 76, 82, 91, 106, 106, 97, 106, 112, 97, 103, 106, 97, 91, 94, 109, 130, 133, 127, 121, 118

Offset

1,7

Comments

When x and y are both 2 or more digits and the larger is L digits long, base b = 10^floor(L/2) is chosen as a split point for those digits with x = xhi*b + xlo and y = yhi*b + ylo.

K(x,y) then makes 3 recursive calls to K(xhi,yhi), K(xlo,ylo) and K(xhi+xlo,yhi+ylo) (and those results can be assembled to make product x*y).

The initial K call and all further recursive calls are counted in a(n).

1 initial call and then 3 recursive calls each time means a(n) == 1 (mod 3).

Links

Table of n, a(n) for n=1..65.

Wikipedia, Karatsuba algorithm

Prog

(Python)
counter = 0
def K(x: int, y: int) -> int:
    global counter; counter += 1
    if x < 10 or y < 10: return x * y
    digits = max(len(str(x)), len(str(y))) // 2
    base = 10 ** digits
    a, b = divmod(x, base)
    c, d = divmod(y, base)
    x = K(b, d)
    y = K(a + b, c + d)
    z = K(a, c)
    return z * 10**(digits * 2) + (y - z - x) * base + x
def a(n: int) -> int:
    from sympy import fibonacci
    global counter; counter = 0
    K(fibonacci(n), fibonacci(n + 1))
    return counter
print([a(n) for n in range(1, 66)])

Crossrefs

Cf. A000045, A055642.

Sequence in context: A023958 A137751 A244481 * A211638 A211639 A010658

Adjacent sequences: A379737 A379738 A379739 * A379741 A379742 A379743

Keyword

nonn

Author

Darío Clavijo, Jan 09 2025

Status

approved