login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A115016 a(n) = smallest number k that has a shortest addition chain whose length A003313(k) = A003313(n*k), or 0 if this never happens. 10
1, 191, 171, 30958077, 3277, 2731, 28087 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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. - N. 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.

REFERENCES

For a comprehensive list of references see A003313.

See also D. E. Knuth, updates to Vol. 2 of TAOCP.

LINKS

Table of n, a(n) for n=1..7.

Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996; p. 61.

N. M. Clift. Calculating optimal addition chains. Computing 91.3 (2011): 265-284.

EXAMPLE

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

CROSSREFS

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

Sequence in context: A238813 A103494 A104642 * A160784 A139650 A139977

Adjacent sequences:  A115013 A115014 A115015 * A115017 A115018 A115019

KEYWORD

hard,nonn

AUTHOR

Hugo Pfoertner, Feb 26 2006

EXTENSIONS

a(4) = 30958077 from N. Clift, May 21 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 09:35 EDT 2019. Contains 322385 sequences. (Running on oeis4.)