A080277 -id:A080277 - cp's OEIS frontend

A038712 Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1.

1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 127, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3

Offset: 1

Henry Bottomley, May 02 2000

n XOR n-1, i.e., nim-sum of a pair of consecutive numbers.
Denominator of quotient sigma(2*n)/sigma(n). - Labos Elemer, Nov 04 2003
a(n) = the Towers of Hanoi disc moved at the n-th move, using standard moves with discs labeled (1, 3, 7, 15, ...) starting from top (smallest = 1). - Gary W. Adamson, Oct 26 2009
Equals row sums of triangle A168312. - Gary W. Adamson, Nov 22 2009
In the binary expansion of n, delete everything left of the rightmost 1 bit, and set all bits to the right of it. - Ralf Stephan, Aug 22 2013
Every finite sequence of positive integers summing to n may be termwise dominated by a subsequence of the first n values in this sequence [see Bannister et al., 2013]. - David Eppstein, Aug 31 2013
Sum of powers of 2 dividing n. - Omar E. Pol, Aug 18 2019
Given the binary expansion of (n-1) as {b[k-1], b[k-2], ..., b[2], b[1], b[0]}, then the binary expansion of a(n) is {bitand(b[k-1], b[k-2], ..., b[2], b[1], b[0]), bitand(b[k-2], ..., b[2], b[1], b[0]), ..., bitand(b[2], b[1], b[0]), bitand(b[1], b[0]), b[0], 1}. Recursively stated - 0th bit (L.S.B) of a(n), a(n)[0] = 1, a(n)[i] = bitand(a(n)[i-1], (n-1)[i-1]), where n[i] = i-th bit in the binary expansion of n. - Chinmaya Dash, Jun 27 2020

			a(6) = 3 because 110 XOR 101 = 11 base 2 = 3.
From _Omar E. Pol_, Aug 18 2019: (Start)
Illustration of initial terms:
a(n) is also the area of the n-th region of an infinite diagram of compositions (ordered partitions) of the positive integers, where the length of the n-th horizontal line segment is equal to A001511(n) and the length of the n-th vertical line segment is equal to A006519(n), as shown below (first eight regions):
-----------------------------
n    a(n)    Diagram
-----------------------------
.            _ _ _ _
1     1     |_| | | |
2     3     |_ _| | |
3     1     |_|   | |
4     7     |_ _ _| |
5     1     |_| |   |
6     3     |_ _|   |
7     1     |_|     |
8    15     |_ _ _ _|
.
The above diagram represents the eight compositions of 4: [1,1,1,1],[2,1,1],[1,2,1],[3,1],[1,1,2],[2,2],[1,3],[4].
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013.
Klaus Brockhaus, Illustration of A038712 and A080277.
David Eppstein, 1317131 and majorization by subsequences.
Fabrizio Frati, M. Patrignani, and V. Roselli, LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs, arXiv preprint arXiv:1610.02841 [cs.CG], 2016.
Malgorzata J. Krawczyk, Paweł Oświęcimka, and Krzysztof Kułakowski, Ordered Avalanches on the Bethe Lattice, Entropy, Vol. 21, (2019) 968.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n.
Index entries for sequences related to Nim-sums.

A038713 translated from binary, diagonals of A003987 on either side of main diagonal.
Cf. A062383. Partial sums give A080277.
Bisection of A089312. Cf. A088837.
a(n)-1 is exponent of 2 in A089893(n).
Cf. A130093.
This is Guy Steele's sequence GS(6, 2) (see A135416).
Cf. A001620, A168312, A220466, A361019 (Dirichlet inverse).

int a(int n) { return n ^ (n-1); } // Russ Cox, May 15 2007

import Data.Bits (xor)
a038712 n = n `xor` (n - 1) :: Integer  -- Reinhard Zumkeller, Apr 23 2012

nmax:=98: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 2^(p+1)-1 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 01 2013
# second Maple program:
a:= n-> Bits[Xor](n, n-1):
seq(a(n), n=1..98);  # Alois P. Heinz, Feb 02 2023

Table[Denominator[DivisorSigma[1, 2*n]/DivisorSigma[1, n]], {n, 1, 128}]
Table[BitXor[(n + 1), n], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

vector(66,n,bitxor(n-1,n)) \\ Joerg Arndt, Sep 01 2013; corrected by Michel Marcus, Aug 02 2018

A038712(n) = ((1<<(1+valuation(n,2)))-1); \\ Antti Karttunen, Nov 24 2024

def A038712(n): return n^(n-1) # Chai Wah Wu, Jul 05 2022

a(n) = A110654(n-1) XOR A008619(n). - Reinhard Zumkeller, Feb 05 2007
a(n) = 2^A001511(n) - 1 = 2*A006519(n) - 1 = 2^(A007814(n)+1) - 1.
Multiplicative with a(2^e) = 2^(e+1)-1, a(p^e) = 1, p > 2. - Vladeta Jovovic, Nov 06 2001; corrected by Jianing Song, Aug 03 2018
Sum_{n>0} a(n)*x^n/(1+x^n) = Sum_{n>0} x^n/(1-x^n). Inverse Moebius transform of A048298. - Vladeta Jovovic, Jan 02 2003
From Ralf Stephan, Jun 15 2003: (Start)
G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^k).
a(2*n+1) = 1, a(2*n) = 2*a(n)+1. (End)
Equals A130093 * [1, 2, 3, ...]. - Gary W. Adamson, May 13 2007
Sum_{i=1..n} (-1)^A000120(n-i)*a(i) = (-1)^(A000120(n)-1)*n. - Vladimir Shevelev, Mar 17 2009
Dirichlet g.f.: zeta(s)/(1 - 2^(1-s)). - R. J. Mathar, Mar 10 2011
a(n) = A086799(2*n) - 2*n. - Reinhard Zumkeller, Aug 07 2011
a((2*n-1)*2^p) = 2^(p+1)-1, p >= 0. - Johannes W. Meijer, Feb 01 2013
a(n) = A000225(A001511(n)). - Omar E. Pol, Aug 31 2013
a(n) = A000203(n)/A000593(n). - Ivan N. Ianakiev and Omar E. Pol, Dec 14 2017
L.g.f.: -log(Product_{k>=0} (1 - x^(2^k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Mar 15 2018
a(n) = 2^(1 + (A183063(n)/A001227(n))) - 1. - Omar E. Pol, Nov 06 2018
a(n) = sigma(n)/(sigma(2*n) - 2*sigma(n)) = 3*sigma(n)/(sigma(4*n) - 4*sigma(n)) = 7*sigma(n)/(sigma(8*n) - 8*sigma(n)), where sigma(n) = A000203(n). - Peter Bala, Jun 10 2022
Sum_{k=1..n} a(k) ~ n*log_2(n) + (1/2 + (gamma - 1)/log(2))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 24 2022
a(n) = Sum_{d divides n} m(d)*phi(d), where m(n) = Sum_{d divides n} (-1)^(d+1)* mobius(d). - Peter Bala, Jan 23 2024

Definition corrected by N. J. A. Sloane, Sep 07 2015 at the suggestion of Marc LeBrun

Name corrected by Wolfdieter Lang, Aug 30 2016

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 40, 41, 41, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48, 49, 49, 50, 51, 52, 52, 53, 54

Offset: 0

Eric W. Weisstein

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.
Least k such that a(k)=n is equal to A003159(n).
To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004
Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011
Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013

			Examples for n = 1 through 8: {1}, {1}, {1,3}, {1,3,4}, {1,3,4,5}, {1,3,4,5}, {1,3,4,5,7}, {1,3,4,5,7}.
Binary expansion of 5 is 101, so Sum{i>=0} b_i*(-1)^i = 2. Therefore a(5) = 10/3 + 2/3 = 4. - _Vladimir Shevelev_, Apr 15 2010

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Double-Free Set.

Bisection of A123087.

Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.

a050292 n = a050292_list !! (n-1)
a050292_list = scanl (+) 0 a035263_list
-- Reinhard Zumkeller, Jan 21 2013

A050292:=n->add((-1)^k*floor(n/2^k), k=0..n); seq(A050292(n), n=0..100); # Wesley Ivan Hurt, Feb 14 2014

a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* Harvey P. Dale, Apr 29 2018 *)

PARI
```
a(n)=if(n<2,1,n-a(floor(n/2)))
```

from sympy.ntheory import digits
def A050292(n): return ((n<<1)+sum((0,1,-1,0)[i] for i in digits(n,4)[1:]))//3 # Chai Wah Wu, Jan 30 2025

Partial sums of A035263. Close to (2/3)*n.
a(n) = A123087(2*n) = n - A123087(n). - Max Alekseyev, Mar 05 2023
From Benoit Cloitre, Nov 24 2002: (Start)
a(1)=1, a(n) = n - a(floor(n/2));
a(n) = (2/3)*n + (1/3)*A065359(n);
more generally, for m>=0, a(2^m*n) - 2^m*a(n) = A001045(m)*A065359(n) where A001045(m) = (2^m - (-1)^m)/3 is the Jacobsthal sequence;
a(A039004(n)) = (2/3)*A039004(n);
a(2*A039004(n)) = 2*a(A039004(n));
a(A003159(n)) = n;
a(A003159(n)-1) = n-1;
a(n) mod 2 = A010060(n) the Thue-Morse sequence;
a(n+1) - a(n) = A035263(n+1);
a(n+2) - a(n) = abs(A029884(n)).
(End)
G.f.: (1/(x-1)) * Sum_{i>=0} (-1)^i*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - Benoit Cloitre, Jun 03 2003
a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - Philippe Deléham, Mar 26 2004
a(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
If n = Sum_{i>=0} b_i*2^i is the binary expansion of n, then a(n) = 2n/3 + (1/3)Sum_{i>=0} b_i*(-1)^i. Thus a(n) = 2n/3 + O(log(n)). - Vladimir Shevelev, Apr 15 2010
Moreover, the equation a(3m)=2m has infinitely many solutions, e.g., a(3*2^k)=2*2^k; on the other hand, a((4^k-1)/3)=(2*(4^k-1))/9+k/3, i.e., limsup |a(n)-2n/3| = infinity. - Vladimir Shevelev, Feb 23 2011
a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - Philippe Deléham, Oct 19 2011
From Peter Bala, Feb 02 2013: (Start)
Product_{n >= 1} (1 + x^((2^n - (-1)^n)/3 )) = (1 + x)^2(1 + x^3)(1 + x^5)(1 + x^11)(1 + x^21)... = 1 + sum {n >= 1} x^a(n) = 1 + 2x + x^2 + x^3 + 2x^4 + 2x^5 + .... Hence this sequence lists the numbers representable as a sum of distinct Jacobsthal numbers A001045 = [1, 1', 3, 5, 11, 21, ...], where we distinguish between the two occurrences of 1 by writing them as 1 and 1'. For example, 9 occurs twice in the present sequence because 9 = 5 + 3 + 1 and 9 = 5 + 3 + 1'. Cf. A197911 and A080277. See also A120385.
(End)

Extended with formula by Christian G. Bower, Sep 15 1999
Corrected and extended by Reinhard Zumkeller, Aug 16 2006
Extended with formula by Philippe Deléham, Oct 19 2011
Entry revised to give a simpler definition by N. J. A. Sloane, Jan 03 2014

A049802 a(n) = n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k <= n < 2^(k+1).

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 4, 0, 3, 4, 7, 4, 7, 8, 11, 0, 4, 6, 10, 8, 12, 14, 18, 8, 12, 14, 18, 16, 20, 22, 26, 0, 5, 8, 13, 12, 17, 20, 25, 16, 21, 24, 29, 28, 33, 36, 41, 16, 21, 24, 29, 28, 33, 36, 41, 32, 37, 40, 45, 44, 49, 52, 57, 0, 6, 10, 16, 16

Offset: 1

Clark Kimberling

nonn

There is the following connection between this sequence and A080277: A080277(n) = n + n*floor(log_2(n)) - a(n). Since A080277(n) is the solution to a prototypical recurrence in the analysis of the algorithm Merge Sort, that is, T(0) := 0, T(n) := 2*T(floor(n/2)) + n, the sequence a(n) seems to be the major obstacle when trying to find a simple, sum-free solution to this recurrence. It seems hard to get rid of the sum. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006

When n = 2^k with k > 0 then a(n+1) = k. For this reason, when n-1 is a Mersenne prime then n - 1 = M(p) = 2^p - 1 = 2^a(n+1) - 1 and p = a(n+1) is prime. - David Morales Marciel, Oct 23 2015

Metin Sariyar, Table of n, a(n) for n = 1..32000 (terms 1..1000 from Paolo P. Lava)
B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3, Example 7.

Cf. A049803, A049804, A070939, A080277, A330358.

f:= proc(n) option remember; local m;
    if n::even then 2*procname(n/2)
    else m:= (n-1)/2; 2*procname(m) + ilog2(m) + 1
    fi
end proc:
f(1):= 0:
map(f, [$1..1000]); # Robert Israel, Oct 23 2015

Table[n * Floor@Log[2,n] - Sum[Floor[n*2^-k]*2^k, {k, Log[2,n]}], {n, 100}] (* Federico Provvedi, Aug 17 2013 *)

a(n) = sum(k=1, logint(n, 2), n % 2^k); \\ Michel Marcus, Dec 12 2019

def a(n): return sum(n % 2**k for k in range(n.bit_length())) # David Radcliffe, May 14 2025

From Robert Israel, Oct 23 2015: (Start)
a(2*n) = 2*a(n).
a(2*n+1) = 2*a(n) + A070939(n) for n >= 1.
G.f. A(x) satisfies A(x) = 2*(1+x)*A(x^2) + (x/(1-x^2))*Sum_{i>=1} x^(2^i). (End)

A136013 a(n) = floor(n/2) + 2*a(floor(n/2)), a(0) = 0.

Original entry on oeis.org

0, 0, 1, 1, 4, 4, 5, 5, 12, 12, 13, 13, 16, 16, 17, 17, 32, 32, 33, 33, 36, 36, 37, 37, 44, 44, 45, 45, 48, 48, 49, 49, 80, 80, 81, 81, 84, 84, 85, 85, 92, 92, 93, 93, 96, 96, 97, 97, 112, 112, 113, 113, 116, 116, 117, 117, 124, 124, 125, 125, 128

Offset: 0

Jack Preston (jpreston(AT)earthlink.net), Mar 20 2008

A recursive sequence that seems to be related to the ruler function.
It seems that a(2n) = a(2n+1) = A080277(n). - Emeric Deutsch, Mar 31 2008
It appears that if the binary expansion of n is n = Sum b_i*2^i (b_i=0 or 1), then a(n) = Sum i*b_i*2^(i-1). - Marc LeBrun, Sep 07 2015
The observations in the preceding two comments (by Emeric Deutsch and Marc LeBrun) follow from the formulas in A333979. - Pontus von Brömssen, Sep 06 2020
This sequence is a variant of the arithmetic derivative (A003415) based on powers of two instead of primes, because the relation  a(m*n) = m*a(n) + n*a(m) holds. If we define the polynomial P(2) = bit0*2^0 + bit1*2^1 + bit2*2^2 + ... = n, and P'(2) is the derivative of P(2), then we will observe P'(2) = a(n). - Thomas Scheuerle, Aug 02 2022

Cf. A080277, A003415, A333979, A135481 (first differences).

a:=proc(n) if n=0 then 0 else floor((1/2)*n)+2*a(floor((1/2)*n)) end if end proc: seq(a(n),n=0..60); # Emeric Deutsch, Mar 31 2008

a = {0}; Do[AppendTo[a, Floor[n/2] + 2*a[[Floor[n/2] + 1]]], {n, 1, 100}]; a (* Stefan Steinerberger, Mar 24 2008 *)
Table[Sum[2^(k-1)*Floor[n*2^-k], {k, 1, Log[2, n]}], {n, 0, 100}] (* Federico Provvedi, Aug 17 2013 *)

a(n) = fromdigits(Vec(Pol(binary(n))'),2); \\ Kevin Ryde, Apr 29 2021

def A136013(n): return sum(map(lambda x:(x[0]+1)*(1<Chai Wah Wu, Jul 06 2022

a(n) = A333979(n,2). - Pontus von Brömssen, Sep 06 2020

More terms from Stefan Steinerberger and Emeric Deutsch, Mar 24 2008

Spelling corrected by Jason G. Wurtzel, Aug 30 2010

A118821 2-adic continued fraction of zero, where a(n) = 2 if n is odd, -A006519(n/2) otherwise.

Original entry on oeis.org

2, -1, 2, -2, 2, -1, 2, -4, 2, -1, 2, -2, 2, -1, 2, -8, 2, -1, 2, -2, 2, -1, 2, -4, 2, -1, 2, -2, 2, -1, 2, -16, 2, -1, 2, -2, 2, -1, 2, -4, 2, -1, 2, -2, 2, -1, 2, -8, 2, -1, 2, -2, 2, -1, 2, -4, 2, -1, 2, -2, 2, -1, 2, -32, 2, -1, 2, -2, 2, -1, 2, -4, 2, -1, 2, -2, 2, -1, 2, -8, 2, -1, 2, -2, 2, -1, 2, -4, 2, -1, 2, -2, 2, -1, 2, -16

Offset: 1

Paul D. Hanna, May 01 2006

Limit of convergents equals zero; only the 6th convergent is indeterminate. Other 2-adic continued fractions of zero are A118824, A118827, A118830. A006519(n) is the highest power of 2 dividing n; A080277 = partial sums of A038712, where A038712(n) = 2*A006519(n) - 1.

			For n >= 1, convergents A118822(k)/A118823(k) are:
  at k = 4*n: -1/A080277(n);
  at k = 4*n+1: -2/(2*A080277(n)-1);
  at k = 4*n+2: -1/(A080277(n)-1);
  at k = 4*n-1: 0/(-1)^n.
Convergents begin:
  2/1, -1/-1, 0/-1, -1/1, -2/1, 1/0, 0/1, 1/-4,
  2/-7, -1/3, 0/-1, -1/5, -2/9, 1/-4, 0/1, 1/-12,
  2/-23, -1/11, 0/-1, -1/13, -2/25, 1/-12, 0/1, 1/-16,
  2/-31, -1/15, 0/-1, -1/17, -2/33, 1/-16, 0/1, 1/-32, ...

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A006519, A080277; convergents: A118822/A118823; variants: A118824, A118827, A118830; A100338.

Array[-2^(IntegerExponent[#, 2] - 1) /. -1/2 -> 2 &, 96] (* Michael De Vlieger, Nov 02 2018 *)

a(n)=local(p=+2,q=-1);if(n%2==1,p,q*2^valuation(n/2,2))

A118824 2-adic continued fraction of zero, where a(n) = -2 if n is odd, A006519(n/2) otherwise.

Original entry on oeis.org

-2, 1, -2, 2, -2, 1, -2, 4, -2, 1, -2, 2, -2, 1, -2, 8, -2, 1, -2, 2, -2, 1, -2, 4, -2, 1, -2, 2, -2, 1, -2, 16, -2, 1, -2, 2, -2, 1, -2, 4, -2, 1, -2, 2, -2, 1, -2, 8, -2, 1, -2, 2, -2, 1, -2, 4, -2, 1, -2, 2, -2, 1, -2, 32, -2, 1, -2, 2, -2, 1, -2, 4, -2, 1, -2, 2, -2, 1, -2, 8, -2, 1, -2, 2, -2, 1, -2, 4, -2, 1, -2, 2, -2, 1, -2, 16, -2, 1, -2, 2, -2, 1

Offset: 1

Paul D. Hanna, May 01 2006

Limit of convergents equals zero; only the 6th convergent is indeterminate. Other 2-adic continued fractions of zero are: A118821, A118827, A118830. A006519(n) is the highest power of 2 dividing n; A080277 = partial sums of A038712, where A038712(n) = 2*A006519(n) - 1.

			For n >= 1, convergents A118825(k)/A118826(k):
  at k = 4*n: 1/A080277(n);
  at k = 4*n+1: 2/(2*A080277(n)-1);
  at k = 4*n+2: 1/(A080277(n)-1);
  at k = 4*n-1: 0.
Convergents begin:
  -2/1, -1/1, 0/-1, -1/-1, 2/1, 1/0, 0/1, 1/4,
  -2/-7, -1/-3, 0/-1, -1/-5, 2/9, 1/4, 0/1, 1/12,
  -2/-23, -1/-11, 0/-1, -1/-13, 2/25, 1/12, 0/1, 1/16,
  -2/-31, -1/-15, 0/-1, -1/-17, 2/33, 1/16, 0/1, 1/32, ...

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A006519, A080277; convergents: A118825/A118826; variants: A118821, A118827, A118830; A100338.

Array[If[OddQ@ #, -2, 2^(IntegerExponent[#, 2] - 1)] &, 102] (* Michael De Vlieger, Nov 06 2018 *)

a(n)=local(p=-2,q=+1);if(n%2==1,p,q*2^valuation(n/2,2))

A118827 2-adic continued fraction of zero, where a(n) = 1 if n is odd, otherwise -2*A006519(n/2).

Original entry on oeis.org

1, -2, 1, -4, 1, -2, 1, -8, 1, -2, 1, -4, 1, -2, 1, -16, 1, -2, 1, -4, 1, -2, 1, -8, 1, -2, 1, -4, 1, -2, 1, -32, 1, -2, 1, -4, 1, -2, 1, -8, 1, -2, 1, -4, 1, -2, 1, -16, 1, -2, 1, -4, 1, -2, 1, -8, 1, -2, 1, -4, 1, -2, 1, -64, 1, -2, 1, -4, 1, -2, 1, -8, 1, -2, 1, -4, 1, -2, 1, -16, 1, -2, 1, -4, 1, -2, 1, -8, 1, -2, 1, -4, 1, -2, 1, -32, 1, -2, 1

Offset: 1

Paul D. Hanna, May 01 2006

Limit of convergents equals zero; only the 6th convergent is indeterminate. Other 2-adic continued fractions of zero are: A118821, A118824, A118830. A006519(n) is the highest power of 2 dividing n; A080277 = partial sums of A038712, where A038712(n) = 2*A006519(n) - 1.

Multiplicative because both A006519 and A165326 are. - Andrew Howroyd, Aug 01 2018

			For n >= 1, convergents A118828(k)/A118829(k):
  at k = 4*n: -1/(2*A080277(n));
  at k = 4*n+1: -1/(2*A080277(n)-1);
  at k = 4*n+2: -1/(2*A080277(n)-2);
  at k = 4*n-1: 0.
Convergents begin:
  1/1, -1/-2, 0/-1, -1/2, -1/1, 1/0, 0/1, 1/-8,
  1/-7, -1/6, 0/-1, -1/10, -1/9, 1/-8, 0/1, 1/-24,
  1/-23, -1/22, 0/-1, -1/26, -1/25, 1/-24, 0/1, 1/-32,
  1/-31, -1/30, 0/-1, -1/34, -1/33, 1/-32, 0/1, 1/-64, ...

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A001620, A006519, A080277; convergents: A118828/A118829; variants: A118821, A118824, A118830; A100338, A165326.

Array[If[OddQ@ #, 1, -2*2^(IntegerExponent[#, 2] - 1)] &, 99] (* Michael De Vlieger, Nov 06 2018 *)

a(n)=local(p=+1,q=-2);if(n%2==1,p,q*2^valuation(n/2,2))

a(n) = A165326(n) * A006519(n). - Andrew Howroyd, Aug 01 2018
From Amiram Eldar, Oct 28 2023: (Start)
Multiplicative with a(2^e) = -2^e, and a(p^e) = 1 for an odd prime p.
Dirichlet g.f.: zeta(s) * (1 - 2^(1-s) + 1/(2-2^s)).
Sum_{k=1..n} a(k) ~ (-1/(2*log(2))) * n *(log(n) + gamma - log(2)/2 - 1), where gamma is Euler's constant (A001620). (End)

A118830 2-adic continued fraction of zero, where a(n) = -1 if n is odd, 2*A006519(n/2) otherwise.

Original entry on oeis.org

-1, 2, -1, 4, -1, 2, -1, 8, -1, 2, -1, 4, -1, 2, -1, 16, -1, 2, -1, 4, -1, 2, -1, 8, -1, 2, -1, 4, -1, 2, -1, 32, -1, 2, -1, 4, -1, 2, -1, 8, -1, 2, -1, 4, -1, 2, -1, 16, -1, 2, -1, 4, -1, 2, -1, 8, -1, 2, -1, 4, -1, 2, -1, 64, -1, 2, -1, 4, -1, 2, -1, 8, -1, 2, -1, 4, -1, 2, -1, 16, -1, 2, -1, 4, -1, 2, -1, 8, -1, 2, -1, 4, -1, 2, -1, 32, -1, 2, -1

Offset: 1

Paul D. Hanna, May 01 2006

Limit of convergents equals zero; only the 6th convergent is indeterminate. Other 2-adic continued fractions of zero are: A118821, A118824, A118827. A006519(n) is the highest power of 2 dividing n; A080277 = partial sums of A038712, where A038712(n) = 2*A006519(n) - 1.

			For n >= 1, convergents A118831(k)/A118832(k):
  at k = 4*n: 1/(2*A080277(n));
  at k = 4*n+1: 1/(2*A080277(n)-1);
  at k = 4*n+2: 1/(2*A080277(n)-2);
  at k = 4*n-1: 0.
Convergents begin:
  -1/1, -1/2, 0/-1, -1/-2, 1/1, 1/0, 0/1, 1/8,
  -1/-7, -1/-6, 0/-1, -1/-10, 1/9, 1/8, 0/1, 1/24,
  -1/-23, -1/-22, 0/-1, -1/-26, 1/25, 1/24, 0/1, 1/32,
  -1/-31, -1/-30, 0/-1, -1/-34, 1/33, 1/32, 0/1, 1/64, ...

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A006519, A080277; convergents: A118831/A118832; variants: A118821, A118824, A118827; A100338.

Array[If[OddQ@ #, -1, 2^IntegerExponent[#, 2]] &, 99] (* Michael De Vlieger, Nov 06 2018 *)

a(n)=local(p=-1,q=+2);if(n%2==1,p,q*2^valuation(n/2,2))

A120385 If a(n-1) = 1 then largest value so far + 1, otherwise floor(a(n-1)/2); or table T(n,k) with T(n,0) = n, T(n,k+1) = floor(T(n,k)/2).

Original entry on oeis.org

1, 2, 1, 3, 1, 4, 2, 1, 5, 2, 1, 6, 3, 1, 7, 3, 1, 8, 4, 2, 1, 9, 4, 2, 1, 10, 5, 2, 1, 11, 5, 2, 1, 12, 6, 3, 1, 13, 6, 3, 1, 14, 7, 3, 1, 15, 7, 3, 1, 16, 8, 4, 2, 1, 17, 8, 4, 2, 1, 18, 9, 4, 2, 1, 19, 9, 4, 2, 1, 20, 10, 5, 2, 1, 21, 10, 5, 2, 1, 22, 11, 5, 2, 1, 23, 11, 5, 2, 1, 24, 12, 6, 3, 1, 25

Offset: 1

Franklin T. Adams-Watters, Jun 29 2006

Although not strictly a fractal sequence as defined in the Kimberling link, this sequence has many fractal properties. If the first instance of each value is removed, the result is the original sequence with each row repeated twice. Removing all odd-indexed instances of each value does give the original sequence.

			The table starts:
  1;
  2, 1;
  3, 1;
  4, 2, 1;
  5, 2, 1;
  6, 3, 1;
  7, 3, 1;
  8, 4, 2, 1;

Alois P. Heinz, Rows n = 1..2048, flattened
C. Kimberling, Fractal sequences

Cf. A029837 (row lengths), A083652 (position of first n).
Cf. A005187 (row sums). A001477, A050292, A080277.
Cf. A000027, A004526, A002265, A132292.

T:= proc(n) T(n):= `if`(n=1, 1, [n, T(iquo(n, 2))][]) end:
seq(T(n), n=1..30);  # Alois P. Heinz, Feb 12 2019

Flatten[Function[n,NestWhile[Append[#, Floor[Last[#]/2]] &, {n}, Last[#] != 1 &]][#] & /@ Range[50]] (* Birkas Gyorgy, Apr 14 2011 *)

T(n,k) = floor(n/2^(k-1)).
From Peter Bala, Feb 02 2013: (Start)
The n-th row polynomial R(n,t) = Sum_{k>=0} t^k*floor(n/2^k) and satisfies the recurrence equation R(n,t) = t*R(floor(n/2),t) + n, with R(1,t) = 1.
O.g.f. Sum_{n>=1} R(n,t)*x^n = 1/(1-x)*Sum_{n>=0} t^n*x^(2^n)/(1 - x^(2^n)).
Product_{n>=1} ( 1 + x^((t^n - 2^n)/(t-2)) ) = 1 + Sum_{n>=1} x^R(n,t) = 1 + x + x^(2 + t) + x^(3 + t) + x^(4 + 2*t + t^2) + .... For related sequences see A050292 (t = -1), A001477(t = 0), A005187 (t = 1) and A080277 (t = 2).
(End)

A118828 Numerators of the convergents of the 2-adic continued fraction of zero given by A118827.

Original entry on oeis.org

1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1, -1, 1, 0, 1, 1, -1, 0, -1

Offset: 1

Paul D. Hanna, May 01 2006

			For n>=1, convergents A118828(k)/A118829(k) are:
at k = 4*n: -1/(2*A080277(n));
at k = 4*n+1: -1/(2*A080277(n)-1);
at k = 4*n+2: -1/(2*A080277(n)-2);
at k = 4*n-1: 0/(-1)^n.
Convergents begin:
1/1, -1/-2, 0/-1, -1/2, -1/1, 1/0, 0/1, 1/-8,
1/-7, -1/6, 0/-1, -1/10, -1/9, 1/-8, 0/1, 1/-24,
1/-23, -1/22, 0/-1, -1/26, -1/25, 1/-24, 0/1, 1/-32,
1/-31, -1/30, 0/-1, -1/34, -1/33, 1/-32, 0/1, 1/-64, ...

Index entries for linear recurrences with constant coefficients, signature (0,0,0,-1).

Cf. A118827 (partial quotients), A118829 (denominators).

seq(signum(mods(n+1, 4)*mods(n+1, 8)), n=1..100); # Peter Luschny, Oct 13 2020

{a(n)=local(p=+1,q=-2,v=vector(n,i,if(i%2==1,p,q*2^valuation(i/2,2)))); contfracpnqn(v)[1,1]}

Period 8 sequence: [1, -1, 0, -1, -1, 1, 0, 1].
G.f.: (1 - x - x^3)/(1 + x^4).
Assuming offset 0 with a(0) = 1, then a has the g.f. (1 + x - x^2)/(1 + x^4) and a(n) = signum(mods(n+1, 4)*mods(n+1, 8)), where mods(a, b) is the symmetric modulo function. - Peter Luschny, Oct 13 2020

cp's OEIS Frontend

A038712 Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A049802 a(n) = n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k <= n < 2^(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A136013 a(n) = floor(n/2) + 2*a(floor(n/2)), a(0) = 0.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A118821 2-adic continued fraction of zero, where a(n) = 2 if n is odd, -A006519(n/2) otherwise.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A118824 2-adic continued fraction of zero, where a(n) = -2 if n is odd, A006519(n/2) otherwise.

Views

Author

Keywords

Comments

Examples

Links