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