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

1, 5, 103, 4985, 641687, 326552783

Offset: 0

Author

Jonathan Vos Post, Jan 26 2010

Keywords

• hard
• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A003586, A018899.

Extensions

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