Dtjytyk

60's-70's movie: home appliances revolting against the owners

Simulating Exploding Dice

Do working physicists consider Newtonian mechanics to be "falsified"?

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

Deal with toxic manager when you can't quit

What aspect of planet Earth must be changed to prevent the industrial revolution?

Python - Fishing Simulator

What force causes entropy to increase?

Didn't get enough time to take a Coding Test - what to do now?

Using dividends to reduce short term capital gains?

What's the point in a preamp?

How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?

How to type a long/em dash `—`

Am I ethically obligated to go into work on an off day if the reason is sudden?

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

Is there a way to generate uniformly distributed points on a sphere from a fixed amount of random real numbers per point?

Does Parliament need to approve the new Brexit delay to 31 October 2019?

One-dimensional Japanese puzzle

Example of compact Riemannian manifold with only one geodesic.

Mortgage adviser recommends a longer term than necessary combined with overpayments

Was credit for the black hole image misappropriated?

Is 'stolen' appropriate word?

Is every episode of "Where are my Pants?" identical?

Is there a writing software that you can sort scenes like slides in PowerPoint?

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