A116459 -id:A116459 - 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.

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)].

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

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