Dtjytyk

Working through the single responsibility principle (SRP) in Python when calls are expensive

What was the last x86 CPU that did not have the x87 floating-point unit built in?

Do I have Disadvantage attacking with an off-hand weapon?

Is 'stolen' appropriate word?

Drawing vertical/oblique lines in Metrical tree (tikz-qtree, tipa)

Can each chord in a progression create its own key?

Make it rain characters

Can I visit the Trinity College (Cambridge) library and see some of their rare books

Was credit for the black hole image misappropriated?

Homework question about an engine pulling a train

"is" operation returns false even though two objects have same id

Simulating Exploding Dice

Single author papers against my advisor's will?

Button changing its text & action. Good or terrible?

Why not take a picture of a closer black hole?

Can the DM override racial traits?

Visa regaring travelling European country

What happens to a Warlock's expended Spell Slots when they gain a Level?

For what reasons would an animal species NOT cross a *horizontal* land bridge?

Presidential Pardon

First use of “packing” as in carrying a gun

Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?

Are spiders unable to hurt humans, especially very small spiders?

Are there continuous functions who are the same in an interval but differ in at least one other point?

Addition chain with two sub-optimal sub-addition chains

0

$begingroup$

An addition chain is a finite sequence of positive integers that starts at $1$, so that any element of the sequence is a sum of two previous elements. That is, it is a sequence $(a_1, ldots, a_k)$ where $a_1 = 1$, and for each $i > 1$ there are $j, k < i$ such that $a_i = a_j + a_k$. An example of an addition chain is
$$
(1, 2, 3, 6, 12, 15).
$$
We call an addition chain that ends in $k$ an addition chain for $k$. We write $l(k)$ for the length of the shorted addition chain for $k$, not counting the 1 at the start of the sequence. Our example above shows that $l(15) leq 5$; in fact $l(15) = 5$.

You can read much more about addition chains on Achim Flammenkamp's page or on Wikipedia.

Write $C(k)$ for the set of addition chains for $k$, and $s(c)$ for the length of a chain $c$ (again not counting the initial 1). Furthermore, we use the notation $c_1 cup c_2$ informally to mean joining the chains $c_1, c_2$ while pruning repeat elements. Then we trivially have
$$
l(k) = min_{i < k \c_1 in C(i)\ c_2 in C(k - i)} s(c_1 cup c_2) + 1.
$$
Now in many cases, we will find that this minimum is not achieved if we restrict to $c_1, c_2$ such that $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$; to achieve maximal overlap, we may want a sequence for one of the summands which is suboptimal. My question is:

Is it possible that we need both subsequences to be suboptimal? That is, is the same minimum attained if we restrict to pairs $(c_1, c_2)$ such that at least one of $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$ holds?

combinatorics recreational-mathematics discrete-optimization

share|cite|improve this question

edited Mar 22 at 13:26

Mees de Vries

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  or mathworld ...
  $endgroup$
  – Roddy MacPhee
  Mar 25 at 13:11
  

  
  
  
  

add a comment | 

0

$begingroup$

An addition chain is a finite sequence of positive integers that starts at $1$, so that any element of the sequence is a sum of two previous elements. That is, it is a sequence $(a_1, ldots, a_k)$ where $a_1 = 1$, and for each $i > 1$ there are $j, k < i$ such that $a_i = a_j + a_k$. An example of an addition chain is
$$
(1, 2, 3, 6, 12, 15).
$$
We call an addition chain that ends in $k$ an addition chain for $k$. We write $l(k)$ for the length of the shorted addition chain for $k$, not counting the 1 at the start of the sequence. Our example above shows that $l(15) leq 5$; in fact $l(15) = 5$.

You can read much more about addition chains on Achim Flammenkamp's page or on Wikipedia.

Write $C(k)$ for the set of addition chains for $k$, and $s(c)$ for the length of a chain $c$ (again not counting the initial 1). Furthermore, we use the notation $c_1 cup c_2$ informally to mean joining the chains $c_1, c_2$ while pruning repeat elements. Then we trivially have
$$
l(k) = min_{i < k \c_1 in C(i)\ c_2 in C(k - i)} s(c_1 cup c_2) + 1.
$$
Now in many cases, we will find that this minimum is not achieved if we restrict to $c_1, c_2$ such that $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$; to achieve maximal overlap, we may want a sequence for one of the summands which is suboptimal. My question is:

Is it possible that we need both subsequences to be suboptimal? That is, is the same minimum attained if we restrict to pairs $(c_1, c_2)$ such that at least one of $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$ holds?

combinatorics recreational-mathematics discrete-optimization

share|cite|improve this question

edited Mar 22 at 13:26

Mees de Vries

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  or mathworld ...
  $endgroup$
  – Roddy MacPhee
  Mar 25 at 13:11
  

  
  
  
  

add a comment | 

$begingroup$

An addition chain is a finite sequence of positive integers that starts at $1$, so that any element of the sequence is a sum of two previous elements. That is, it is a sequence $(a_1, ldots, a_k)$ where $a_1 = 1$, and for each $i > 1$ there are $j, k < i$ such that $a_i = a_j + a_k$. An example of an addition chain is
$$
(1, 2, 3, 6, 12, 15).
$$
We call an addition chain that ends in $k$ an addition chain for $k$. We write $l(k)$ for the length of the shorted addition chain for $k$, not counting the 1 at the start of the sequence. Our example above shows that $l(15) leq 5$; in fact $l(15) = 5$.

You can read much more about addition chains on Achim Flammenkamp's page or on Wikipedia.

Write $C(k)$ for the set of addition chains for $k$, and $s(c)$ for the length of a chain $c$ (again not counting the initial 1). Furthermore, we use the notation $c_1 cup c_2$ informally to mean joining the chains $c_1, c_2$ while pruning repeat elements. Then we trivially have
$$
l(k) = min_{i < k \c_1 in C(i)\ c_2 in C(k - i)} s(c_1 cup c_2) + 1.
$$
Now in many cases, we will find that this minimum is not achieved if we restrict to $c_1, c_2$ such that $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$; to achieve maximal overlap, we may want a sequence for one of the summands which is suboptimal. My question is:

Is it possible that we need both subsequences to be suboptimal? That is, is the same minimum attained if we restrict to pairs $(c_1, c_2)$ such that at least one of $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$ holds?

combinatorics recreational-mathematics discrete-optimization

share|cite|improve this question

edited Mar 22 at 13:26

Mees de Vries

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060

$endgroup$

share|cite|improve this question

edited Mar 22 at 13:26

Mees de Vries

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060

share|cite|improve this question

edited Mar 22 at 13:26

Mees de Vries

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060

asked Mar 22 at 13:21

Mees de VriesMees de Vries

17.6k13060