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.

%I A115016 #23 Sep 10 2024 20:47:14
%S A115016 1,191,171,30958077,3277,2731,28087
%N 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.
%C A115016 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
%C A115016 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.
%D A115016 For a comprehensive list of references see A003313.
%D A115016 See also D. E. Knuth, updates to Vol. 2 of TAOCP.
%H A115016 Daniel Bleichenbacher, <a href="http://cr.yp.to/bib/1996/bleichenbacher-thesis.ps">Efficiency and Security of Cryptosystems based on Number Theory</a>, PhD Thesis, Diss. ETH No. 11404, Zürich 1996; p. 61.
%H A115016 Neill Michael Clift, <a href="https://doi.org/10.1007/s00607-010-0118-8">Calculating optimal addition chains</a>, Computing 91.3 (2011): 265-284.
%e A115016 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].
%Y A115016 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)].
%K A115016 nonn,hard,more
%O A115016 1,2
%A A115016 _Hugo Pfoertner_, Feb 26 2006
%E A115016 a(4) from _Neill M. Clift_, May 21 2008