A003313 -id:A003313 - cp's OEIS frontend

A086878 Numbers n such that A003313(n) = A003313(2n).

191, 701, 743, 1111, 1389, 1479, 2103, 2215, 2375, 2681, 2951, 4281, 4423, 4491, 4743, 5337, 5517, 5895, 6319, 6367, 6491, 6703, 6751, 7247, 7319, 7463, 7481, 7571, 7751, 7909, 7993, 8043, 8083, 8269, 8425, 8537, 8839, 8853, 8971, 9479, 10481

Offset: 1

Pontus von Brömssen, Sep 16 2003

nonn

Hugo Pfoertner, Table of n, a(n) for n = 1..10000
E. G. Thurber, Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1, Discrete Math., Vol. 16 (1976), 279-289.

Cf. A003313, A230528.

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.

Original entry on oeis.org

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.

A076091 Numbers n such that A064097(n) - A003313(n) = 1.

Original entry on oeis.org

23, 33, 43, 46, 47, 49, 59, 65, 66, 67, 69, 77, 83, 86, 92, 94, 98, 99, 107, 115, 118, 121, 130, 131, 132, 133, 134, 138, 139, 141, 145, 147, 149, 154, 163, 165, 166, 167, 172, 173, 177, 179, 184, 188, 195, 196, 197, 198, 199, 201, 203, 207, 209

Offset: 1

Benoit Cloitre, Oct 31 2002

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000 (also based on the b-file of A003313 provided by D. W. Wilson and Antoine Mathys)

Cf. A003313, A064097, A076142.

Corrected and extended by Hugo Pfoertner, Feb 17 2006

A076142 a(n) = A064097(n) - A003313(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2

Offset: 1

Benoit Cloitre, Oct 31 2002

nonn

The positions where k = 0, 1, 2, ... occur for the first time are 1, 23, 129, 517, 2049, 4613, 33097, 33793, ... factorized as: 1, 23, 3*43, 11*47, 3*683, 7*659, 23*1439, 47*719, ... - Antti Karttunen, Aug 18 2017

Antti Karttunen, Table of n, a(n) for n = 1..10000 (also based on the b-file of A003313)

Cf. A003313, A064097, A076091.

It seems that sum(k = 1, n, a(k)) * log(n)/n^2 -> c (0.006 < c < 0.01).

Extended to 129 terms by Antti Karttunen, Aug 18 2017

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

cp's OEIS Frontend

A086878 Numbers n such that A003313(n) = A003313(2n).

Views

Author

Keywords

Links

Crossrefs

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

A076091 Numbers n such that A064097(n) - A003313(n) = 1.

Views

Author

Keywords

Links

Crossrefs

Extensions

A076142 a(n) = A064097(n) - A003313(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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