Addition Sequence

Problem description:

It was stated on IntegerPowerAlgorithm that a good algorithm is using the multiply-or-square algorithm (check the top of the page). Someone then suggested that for some cases cubing is better (I.e. for x to the power 27, let a = x*x, let b = a*x, let c = b*b, let d = b*c, let e = d*d and let result = d*e, this is 6 multiplications instead of the 8 needed by the multiply-or-square-algorithm)

Then the topic came up that there was a general system of this, and that in the end, one would just need to find the solution for the following problem.

Given a positive integer(power) n, let f(n) be the smallest k such that there is a sequence

  1 = a_0, a_1, ..., a_k = n,

Somehow I felt that people thought that this problem was unsolvable and that it would be more efficient than the multiply-or-square algorithm for finding a power of a certain number. I'd like to state here how to find it and prove that this is not so. In the end, I'll try to prove that finding the sequence the shortest sequences as dictated above takes the same amount of time as finding the prime-divisors of k, which in my book is still O(sqrt(k)).

Finding the factors of k, for large k, can be done in time of order exp(K*L1^a*L2^b) where K is a constant, L1 = log k, and L2 = log log k; the best algorithm currently known for large k is the number field sieve, which has K<2, a=1/3, b=2/3; for smaller k it's better in practice to use the multiple-polynomial quadratic sieve, which has K=1, a=1/2, b=1/2. For even smaller k, the elliptic curve method may be better; it has K=2, a=1/2, b=1/2 but the constant in front of exp(...) is smaller. All these are much better than sqrt(k). Of course they're also a lot worse than the time it takes to just do the exponentiation using the squaring algorithm.

Preamble:

This is the official definition that was used above

Official Definition: addition sequence

An addition sequence is a sequence starting with a certain value 'a' where each element is the sum of two prior elements (not specifically the two just before it like the FibonacciSequence, neither specifically two different elements):

    a=a_0, a_1, ...., a_n

where

    each a_k = a_i + a_j for some i,j where 0<=i<k and 0<=j<k

Introduction:

The following are my own definitions and theorems to be used in the proof.

Definition: partially ordered addition sequence

A partially ordered addition sequence is an addition sequence with the additional property that:

    a_i <= a_j for all i,j where i < j

Definition: ordered addition sequence

An ordered addition sequence is an addition sequence with the additional property that:

    a_i < a_j for all i,j where i < j

That is, a partially ordered addition sequence with no duplicates.

Lemma 1:

Any addition sequence has an equivalent partially ordered addition sequence.

Proof:

Whenever 2 consecutive elements a_j, a_(j+1) in an addition sequence are out-of-order (whenever a_(j+1) is less than a_j), they can be put in order by swapping them. (When a_(j+1) < a_j, then a_(j+1) cannot be the sum of a_j and some other element a_i where i < (j+1).)

By repeatedly swapping elements that are out-of-order, eventually the sequence can be sorted into a partially ordered addition sequence.

Lemma 2:

Any addition sequence without duplicates has an equivalent ordered addition sequence.

Proof:

The proof for this is trivial. It follows from Lemma 1 and the definition of an ordered addition sequence .

Lemma 3:

An addition sequence f(n) that has to fulfil the property of being the shortest sequence with f(n)=k for some given k:

    1=a_0,a_1,...,a_n=k with n as small as possible

can always be transformed into an ordered addition sequence.

Proof:

The proof for this is trivial, it follows from Lemma 2 and the fact that the shortest addition sequence fulfilling the criteria will not have any duplicate elements as they're not necessary.

Ok, since I'm going quite slow at this I'll try to put the idea of my proof, perhaps someone can help who's better than this. When constructing some element a_k, taking elements with greater indices in an ordered addition sequence will result in a bigger a_k. It's obvious that an ordered addition sequence is a strictly increasing sequence of integers, plus we're limiting it to a certain number, so it MUST converge. Now if we can find SPLITS, aka places where all a_k with k > than some n are only formed of elements a_i with i >= n, then it's obvious all those a_k's are multiples of a_n... Now since taking numbers from bigger indices to construct a number gives you a bigger number, this means that constructing a number from just the number before it gives you the biggest number (this is also the reason why the following sequence leads to the biggest number: 1=a_0, a_1 = 2* a_0, ....a_k = 2*a_k, and this is also the reason why a_k <= 2^k). Well, if you find such a SPLIT, you're basically working in function of a multiple of a number, so you're starting a new addition series with a_0 equal to the number. If I can prove that working with SPLITS is the shortest way (because we take as big numbers as possible to construe the next one), it's obvious that the n of f(n) = k is equal to the sum of n_i where f(n_i) = p_i with p_i being a prime factor of k. For example.... 12=2*2*3...so the shortest addition series length will be the n for f(n) = 2 + n for f(n) = 2 + for f(n) = 3....in this case: 1 + 1 + 2 = 4).

This is a work in progress, I'm too tired to continue at the moment, but I'll finish soon. -- ChristophePoucet?

Some special cases:

The shortest addition sequence to get to k where k is some power of 2 (k = 2^n) is always doubling the previous number f(n) = 2*f(n-1), which implies repeated squaring. (There is no other addition sequence that even gives the same number of steps).

The shortest addition sequence to get to k where k is a Fibonacci number ...

I think the next step is to prove that given any addition sequence, and given some prime p_i that is a factor of the final desired number, there is some ordered addition sequence that *does* have a SPLIT that either has the same or fewer number of steps.

Lemma 3 converts that addition sequence to an ordered addition sequence.

Given some ordered addition sequence that does *not* have a split (in other words, a_n = a_0 + a_i), it can be converted to an ordered addition sequence (with the same or fewer number of steps), and also has a split, by ...

This is also handled in TheArtOfComputerProgramming, though I can't give you the exact pages, but it is in SeminumericalAlgorithms?.