login
A145812
Odd positive integers a(n) such that for every odd integer m > 1 there exists a unique representation of m as a sum of the form a(l) + 2a(s).
17
1, 3, 9, 11, 33, 35, 41, 43, 129, 131, 137, 139, 161, 163, 169, 171, 513, 515, 521, 523, 545, 547, 553, 555, 641, 643, 649, 651, 673, 675, 681, 683, 2049, 2051, 2057, 2059, 2081, 2083, 2089, 2091, 2177, 2179, 2185, 2187, 2209, 2211, 2217, 2219, 2561, 2563
OFFSET
1,2
COMMENTS
Theorem. An odd number is in the sequence iff in its binary expansion all digits on k-th positions from the end, k=3, 5, 7, ..., are zeros. For example, 169, 171 have binary expansions 10101001, 10101011. Thus both of them are in the sequence. If A(x) is the counting function of a(n) <= x, then A(x) = O(sqrt(x)) and Omega(sqrt(x)).
Every positive odd integer m==3 (mod 2^(2r-1)) is a unique sum of the form a(2^(r-1)*(s-1)+1) + 2a(2^(r-1)*(t-1)+1), r=1,2,..., while the other odd integers are not expressible in such a form (see also the comment to A145818). Problem: Let B be the set of analytical functions f(x), f(0)=0, abs(x) > 1, with (0,1)-Taylor coefficients. Let F(x) be in B. It could be proved that the equation f(x)*f(x^2) = F(x) has no more than one solution in B. In case of F(x) = x^3/(1-x^(2^r)), r=1,2,..., it has one solution, which leads to A145812, A145818, A145849, A145850, etc. Find the conditions of the solvability of this equation in B and give, if it is possible, other examples. [Vladimir Shevelev, Oct 21 2008]
To get the decomposition of odd m as sum a(l) + 2a(s), write m-2 as Sum b_j 2^j, then a(l) = 1 + Sum_{j odd} b_j 2^j. This algorithm follows from our comment to A088442 and the algorithm of calculation of A088442(n). For example, if m=81, then we have 79 = 1*2^0 + 1*2^1 + 1*2^2 + 1*2^3 + 1*2^6. Thus a(l) = 1 + (1*2^1 + 1*2^3) = 11 and the required decomposition is 81 = 11 + 2*35, such that a(s)=35. We see that L=4, s=6, i.e., "index coordinates" of 81 are (4,6). Thus we have a one-to-one map of odd integers > 1 to the positive lattice points in the plane. [Vladimir Shevelev, Oct 24 2008]
LINKS
FORMULA
If f(x) = Sum_{n>=1} x^a(n), abs(x) < 1, then f(x)*f(x^2) = x^3/(1-x^2).
To get a(n), write n-1 as Sum b_j 2^j, then a(n) = 1 + 2Sum b_j 2^(2j). Conversely, if an odd number m==r(mod 4), r=1 or 3 has the form which is indicated in the theorem, i.e., 2m - 2r = Sum_{j>=1} b_j 2^(2j), b_j = 0 or 1, then the only solution of the equation a(x)=m is x = Sum_{j>=1} b_j 2^(j-1) + (r+1)/2. [Vladimir Shevelev, Oct 25 2008]
For n >= 2, a(n) = a(n-1) + (4^(t+1) + 2)/3, where t >= 0 is such that n-1 == 2^t (mod 2^(t+1)). [Vladimir Shevelev, Nov 04 2008]
a(n) = 2*A000695(n-1) + 1. [Vladimir Shevelev, Nov 07 2008]
From Robert Israel, Aug 20 2017: (Start)
a(2n-1) = 4*a(n)-3.
a(2n) = 4*a(n)-1.
G.f. g(z) satisfies g(z) = (4 + 4/z) g(z^2) - (z^2 + 3 z)/(1-z^2). (End)
EXAMPLE
If n=13, we have n-1 = 12 = 2^3 + 2^2. Therefore a(13) = 1 + 2(4^3 + 4^2) = 161. If m=521 and thus 2(521-1) = 1040 = 2^10 + 2^4, then the equation a(x)=521 has the unique solution x = 2^4 + 2^1 + 1 = 19. [Vladimir Shevelev, Oct 25 2008]
MAPLE
filter:= proc(n) local L; L:= convert(n, base, 2);
andmap(i -> L[2*i+1]=0, [$1..(nops(L)-1)/2])
end proc:
select(filter, [seq(i, i=1..10000, 2)]); # Robert Israel, Aug 20 2017
MATHEMATICA
a[1]=1; a[2]=3; a[n_] := a[n] = If[OddQ[n], 4*a[(n+1)/2]-3, 4*a[n/2]-1];
Array[a, 50] (* Jean-François Alcover, Nov 14 2017, after Robert Israel *)
PROG
(PARI) isok(n) = {if (! (n % 2), return (0)); b = binary(n); forstep (i = #b, 1, -1, rpos = #b - i + 1; if ((rpos > 1) && (rpos % 2) && b[i], return (0)); ); return (1); } \\ Michel Marcus, Jan 19 2014
(Haskell)
a145812 n = a145812_list !! (n-1)
a145812_list = filter f [1, 3 ..] where
f v = v == 0 || even w && f w where w = v `div` 4
-- Reinhard Zumkeller, Mar 13 2014
CROSSREFS
Cf. A000695.
Sequence in context: A272737 A273533 A268033 * A220944 A200879 A027895
KEYWORD
nonn,look
AUTHOR
Vladimir Shevelev, Oct 20 2008
EXTENSIONS
Extended beyond a(16) by Klaus Brockhaus, Oct 22 2008
STATUS
approved