A360303 a(n) = Sum_{k=1..floor(sqrt(n))} 2^floor(n/k-k).

0, 1, 2, 4, 9, 17, 34, 66, 132, 261, 521, 1033, 2066, 4114, 8226, 16420, 32837, 65605, 131209, 262281, 524554, 1048850, 2097682, 4194834, 8389668, 16778277, 33556517, 67110981, 134221897, 268439625, 536879242, 1073750154, 2147500178, 4294983954, 8589967634, 17179902228, 34359804453

Offset: 0

Author

Luc Rousseau, Feb 02 2023

Keywords

• nonn
• base

Comments

This sequence corresponds to the left half of a drawing, the whole drawing being reconstituted by symmetry (see the Illustration link). The divisors of n are closely related to the occurrences of the bit pattern "01 over 10" in the 2 X 2 squares along the (n-1)th and n-th lines (see the pattern link). In particular, n is a prime number if and only if a(n) - a(n-1) = 2^(n-2).

Examples

			For n = 5, floor(sqrt(n)) = 2. So, two bits are set in a(n); they are the bits number floor(5/1-1)=4 and floor(5/2-2)=0, so a(n) = 10001_2 = 17.
		

Links

• Luc Rousseau, Illustration in black and white, n = 0..100.
• Luc Rousseau, Illustrated bit pattern for the detection of divisors, n = 1..9.

Crossrefs

Cf. A034729.

Programs

PARI

a(n)=sum(k=1,floor(sqrt(n)),2^floor(n/k-k))

Formula

a(n) = Sum_{k=1..floor(sqrt(n))} 2^floor(n/k - k).