A086878 -id:A086878 - cp's OEIS frontend

A115016 a(n) is the smallest number k that has a shortest addition chain whose length A003313(k) = A003313(n*k), or 0 if this never happens.

1, 191, 171, 30958077, 3277, 2731, 28087

Offset: 1

Hugo Pfoertner, Feb 26 2006

Using ? to indicate a term whose value is presently unknown, the sequence reads 1, 191, 171, 30958077, 3277, 2731, 28087, ?, 233017, 432541, 953251, 699051, 12905551, 1797559, ?, ?, ?, ?, 7064091, ... This is based on several years work using a variety of algorithms. - Neill M. Clift, May 23 2008

It was conjectured that no shortest addition chains exist such that A003313(m)=A003313(m*2^k) for k>1. This is now known to be false, since a(4) != 0.

			a(3)=171 because 171 and 513=3*171 both have a shortest addition chain of length 10. 171 and 513 is the smallest pair of numbers with the property A003313(k)=A003313(3*k). Examples for the corresponding shortest chains are [1 2 4 5 7 14 19 38 57 114 171] and [1 2 4 8 16 32 64 128 256 512 513].

For a comprehensive list of references see A003313.
See also D. E. Knuth, updates to Vol. 2 of TAOCP.

Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, PhD Thesis, Diss. ETH No. 11404, Zürich 1996; p. 61.
Neill Michael Clift, Calculating optimal addition chains, Computing 91.3 (2011): 265-284.

Cf. A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A261986 [l(k)=l(4*k)], A116460 [l(k)=l(5*k)], A116461 [l(k)=l(6*k)], A116462 [l(k)=l(7*k)], A116463 [l(k)=l(9*k)], A117151 [l(k)=l(10*k)].

a(4) from Neill M. Clift, May 21 2008

A116461 Numbers k such that A003313(k) = A003313(6*k).

Original entry on oeis.org

2731, 5462, 10923, 10924, 13655, 21846, 21848, 27307, 27310, 43691, 43692, 43696, 54614, 54615, 54620, 71003, 87382, 87384, 87392, 92843, 109227, 109228, 109230, 109240, 133819, 142006, 152919, 174763, 174764, 174768, 174784, 177515, 185686, 185691, 218454

Offset: 1

Hugo Pfoertner, Mar 07 2006

nonn

The first 20 terms are identical to those given in Table 4.5, "The set of values m satisfying l(3m)A104699). Only 109227 is not in Table 4.5.

The first 82 terms are identical to those of A104699, but A104699(83)=699051, for which A003313(3*699051)=22, is not in the current sequence, because A003313(6*699051)=23 < A003313(699051)=24. - Hugo Pfoertner, Dec 19 2015

Hugo Pfoertner, Table of n, a(n) for n = 1..10000
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 61.

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A261986 [l(k)=l(4*k)], A116460 [l(k)=l(5*k)], A116462 [l(k)=l(7*k)], A116463 [l(k)=l(9*k)], A117151 [l(k)=l(10*k)].

Cf. A104699.

A116459 Numbers k such that A003313(k) = A003313(3*k).

Original entry on oeis.org

171, 342, 427, 683, 684, 854, 855, 1111, 1195, 1366, 1367, 1368, 1451, 1707, 1708, 1710, 2390, 2732, 2734, 2736, 2902, 3414, 3415, 3416, 3420, 3755, 4203, 4271, 4780, 4781, 5463, 5464, 5468, 5472, 5483, 5803, 5804, 6319, 6331, 6383, 6491, 6827, 6828

Offset: 1

Hugo Pfoertner, Mar 07 2006

nonn

			a(3)=427 because both 427 and 1281=3*427 have associated shortest addition chains of length 12: [1,2,4,8,16,17,34,68,136,137,145,290,427] and [1,2,4,5,10,20,40,80,160,320,640,1280]. This is the third occurrence of such a pair. The first two are (171,513) and (342,1026).

Hugo Pfoertner, Table of n, a(n) for n = 1..10000

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A261986 [l(k)=l(4*k)], A116460 [l(k)=l(5*k)], A116461 [l(k)=l(6*k)], A116462 [l(k)=l(7*k)], A116463 [l(k)=l(9*k)], A117151 [l(k)=l(10*k)].

A116460 Numbers k such that A003313(k) = A003313(5*k).

Original entry on oeis.org

3277, 6554, 9831, 13108, 19661, 19662, 22939, 26216, 27037, 27853, 29493, 39322, 39324, 44237, 45878, 52429, 52432, 54074, 55706, 55709, 58983, 58986, 72091, 78644, 78648, 81111, 88474, 88479, 91756, 104858, 104861, 104864, 105293, 105677, 108141, 108148, 111412

Offset: 1

Hugo Pfoertner, Mar 07 2006

nonn

Hugo Pfoertner, Table of n, a(n) for n = 1..10000

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A261986 [l(k)=l(4*k)], A116461 [l(k)=l(6*k)], A116462 [l(k)=l(7*k)], A116463 [l(k)=l(9*k)], A117151 [l(k)=l(10*k)].

A116462 Numbers k such that A003313(k) = A003313(7*k).

Original entry on oeis.org

28087, 56174, 93623, 112348, 149815, 150967, 159159, 187246, 224695, 224696, 299630, 299959, 301943, 318318, 318319, 337043, 374492, 449390, 449392, 468119, 486839, 599191, 599260, 599479, 599918, 601527, 603886, 617911, 636636, 636638, 674086, 748983, 748984

Offset: 1

Hugo Pfoertner, Mar 07 2006

nonn

Hugo Pfoertner, Table of n, a(n) for n = 1..4784

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A261986 [l(k)=l(4*k)], A116460 [l(k)=l(5*k)], A116461 [l(k)=l(6*k)], A116463 [l(k)=l(9*k)], A117151 [l(k)=l(10*k)].

A116463 Numbers k such that A003313(k) = A003313(9*k).

Original entry on oeis.org

233017, 466034, 699051, 932068, 1165085, 1398102, 1864136, 1878713, 1922393, 2330169, 2330170, 2796203, 2796204, 3262237, 3495255, 3728272, 3757426, 3844786, 3961289, 4660338, 4660340, 5359389, 5592406, 5592408, 5708921, 5941931, 6524474, 6990507, 6990510, 7456544

Offset: 1

Hugo Pfoertner, Mar 07 2006

nonn

The sequence is based on data computed by Neill M. Clift.

Hugo Pfoertner, Table of n, a(n) for n = 1..463

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A261986 [l(k)=l(4*k)], A116460 [l(k)=l(5*k)], A116461 [l(k)=l(6*k)], A116462 [l(k)=l(7*k)], A117151 [l(k)=l(10*k)].

More terms from Hugo Pfoertner, Sep 07 2015

A117151 Numbers k such that A003313(k) = A003313(10*k).

Original entry on oeis.org

432541, 838861, 865082, 1468007, 1677722, 1730164, 1887437, 2516583, 2726299, 2936014, 3355444, 3460301, 3460328, 3774874, 5033165, 5033166, 5452598, 5872027, 5872028, 6710888, 6920602, 6920605, 6920656, 7130317, 7549748, 7549749, 10066330, 10066332, 10905191

Offset: 1

Hugo Pfoertner, Mar 07 2006

nonn

The sequence is based on data computed by Neill M. Clift.

Hugo Pfoertner, Table of n, a(n) for n = 1..276

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A261986 [l(k)=l(4*k)], A116460 [l(k)=l(5*k)], A116461 [l(k)=l(6*k)], A116462 [l(k)=l(7*k)], A116463[l(k)=l(9*k)].

More terms from Hugo Pfoertner, Sep 07 2015

A261986 Numbers k such that A003313(k) = A003313(4*k).

Original entry on oeis.org

30958077, 55670941, 61487077, 111031197, 112710897, 113180303, 114523591, 121275479, 121963055, 122830789, 215074411, 215182221, 220162873, 222034845, 222254557, 222661789, 223538781, 225298237, 225414385, 225545245, 225695631, 225718029, 226254877, 226356879

Offset: 1

Hugo Pfoertner, Sep 07 2015

nonn

Terms are counterexamples to the conjecture that no shortest addition chains exist such that A003313(m)=A003313(m*2^k) for k>1, with a(1)=30958077 provided in 2008 by Neill M. Clift.

Hugo Pfoertner, Table of n, a(n) for n = 1..75

Cf. A115016, A003313 [l(k)], A086878 [l(k)=l(2*k)], A116459 [l(k)=l(3*k)], A116460 [l(k)=l(5*k)], A116461 [l(k)=l(6*k)], A116462 [l(k)=l(7*k)], A116463 [l(k)=l(9*k)], A117151 [l(k)=l(10*k)].

A230528 Numbers k such that a shortest addition chain for 2k is shorter than one for k, that is, A003313(2k) < A003313(k).

Original entry on oeis.org

375494703, 602641031, 619418303, 728117339, 750793519, 750832687, 750989359

Offset: 1

Max Alekseyev, Oct 22 2013

Can the shortest addition chain for 2*k be shorter than one for k by more than 1? - Alexey Slizkov, Jan 20 2024

Neill Michael Clift, Calculating optimal addition chains, Computing 91.3 (2011): 265-284.
V. Zhuravlev and P. Samovol, Faster than the fastest, or can one beat the binary algorithm, Kvant 2 (2013), 7-15. (in Russian)

Cf. A003313, A086878, A115016, A256653.

a(1) = 375494703 was found by Neill M. Clift (2011)

a(2)-a(7) from Hugo Pfoertner, Dec 19 2015

cp's OEIS Frontend

A115016 a(n) is the smallest number k that has a shortest addition chain whose length A003313(k) = A003313(n*k), or 0 if this never happens.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A116461 Numbers k such that A003313(k) = A003313(6*k).

Views

Author

Keywords

Comments

Links

Crossrefs

A116459 Numbers k such that A003313(k) = A003313(3*k).

Views

Author

Keywords

Examples

Links

Crossrefs

A116460 Numbers k such that A003313(k) = A003313(5*k).

Views

Author

Keywords

Links

Crossrefs

A116462 Numbers k such that A003313(k) = A003313(7*k).

Views

Author

Keywords

Links

Crossrefs

A116463 Numbers k such that A003313(k) = A003313(9*k).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A117151 Numbers k such that A003313(k) = A003313(10*k).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A261986 Numbers k such that A003313(k) = A003313(4*k).

Views

Author

Keywords

Comments

Links

Crossrefs

A230528 Numbers k such that a shortest addition chain for 2*k is shorter than one for k, that is, A003313(2*k) < A003313(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A230528 Numbers k such that a shortest addition chain for 2k is shorter than one for k, that is, A003313(2k) < A003313(k).