A245470 Smallest multiple of n such that, when expressed in binary, in the string of bits the binary representation of n occurs after the n-1 most significant bits.

1, 6, 15, 36, 85, 150, 287, 1032, 2169, 4170, 8283, 16428, 32877, 65646, 131295, 524304, 1048849, 2097234, 4194611, 8388660, 16777845, 33554774, 67109239, 134217816, 268436025, 536871322, 1073742075, 2147483772, 4294967773, 8589935070, 17179869695, 68719476768, 137438955489, 274877908002, 549755814755, 1099511627940

Offset: 1

Author

Franklin T. Adams-Watters, Jul 25 2014

Keywords

• nonn
• base

Comments

For n>1, let d be the number of bits in n, and n' = n/gcd(n,2^d) = n/2^valuation(n,2) = A000265(n). Then a(n) = (2^{n-2}+mod(-(2^{n-2}),n')) * 2^d + n. (The mod function used here always returns a nonnegative result; e.g. mod(-2,7) = 5.) The alternative to use n/p^valuation(n,p) instead of gcd(n,p^d) works in any prime base p.

The word "after" in the definition can be interpreted as either "immediately after" or "at some point after" - the resulting sequence is the same.

Examples

			a(4) = 36 = 100100_2; 100, the binary representation of 4, occurs after 4-1 = 3 bits.
		

Crossrefs

Cf. A079847, A000265.

Programs

PARI

numbit(n)=my(r=1); while(n>=2, n\=2; r++); r a(n) = my(k, m); if(n<=1, n, k=2^numbit(n); m=2^(n-2); (-m%(n\gcd(n,k))+m)*k+n) \\ Could use 2^valuation(n,2) instead of gcd(n,k).