A172116 The smallest number without double base representation of length n.

1, 5, 103, 4985, 641687, 326552783

Offset

0,2

Comments

Portion of abstract from Dimitrov/Howe reference: A double-base representation of an integer n is an expression n = n_1 + ... + n_r, where the n_i are (positive or negative) integers that are divisible by no primes other than 2 or 3; the length of the representation is the number r of terms. It is known that there is a constant a > 0 such that every integer n has a double-base representation of length at most a log n / log log n.

Links

Table of n, a(n) for n=0..5.

Vassil S. Dimitrov and Everett W. Howe, Lower bounds on the lengths of double-base representations, Proc. Amer. Math. Soc. 139 (2011), 3423-3430. Also arXiv:1001.4133.

Vassil S. Dimitrov and Everett W. Howe, Magma and C programs verifying these entries

Vassil Dimitrov, Laurent Imbert, and Pradeep Kumar Mishra, Efficient and secure elliptic curve point multiplication using double-base chains, Advances in cryptology, ASIACRYPT 2005, Lecture Notes in Comput. Sci., vol. 3788, Springer, Berlin, 2005, pp. 59-78.

Vassil Dimitrov, Laurent Imbert, and Pradeep K. Mishra, The double-base number system and its application to elliptic curve cryptography, Math. Comp. 77 (2008), no. 262, 1075-1104.

Pradeep Kumar Mishra and Vassil Dimitrov, A combinatorial interpretation of double base number system and some consequences, Adv. Math. Commun. 2 (2008), no. 2, 159-173.

Example

For example, 103 can be written in many ways as the sum of 3 integers, each with no prime divisors other than 2 and 3 (e.g. 103 = (-1) + (-4) + 108), but it cannot be written as the sum of 2 such integers.  103 is the smallest positive integer that requires more than 2 terms.

Crossrefs

Cf. A003586, A018899.

Sequence in context: A308459 A142418 A159523 * A007619 A163212 A163154

Adjacent sequences: A172113 A172114 A172115 * A172117 A172118 A172119

Keyword

hard,nonn

Author

Jonathan Vos Post, Jan 26 2010

Extensions

Prepended initial terms, updated references, modified comment, added example by Everett W. Howe, Jun 05 2015

Status

approved