Displaying 1-10 of 63 results found.
Denote the van der Corput sequence of fractions 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, ... ( A030101/ A062383) by v(n), n >= 1. Then a(n) = denominator of v( A014486(n)).
+20
2
4, 16, 16, 64, 64, 64, 64, 64, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024, 1024
COMMENTS
The initial values suggest the conjecture that this sequence consists exactly of Catalan(n) copies of 4^k for k >= 1.
Hugo Pfoertner tested this conjecture with the PARI program given below.
Here is the output from that program:
[1, 0, 4]
[2, 4, 16]
[4, 16, 64]
[9, 64, 256]
[23, 256, 1024]
[65, 1024, 4096]
[197, 4096, 16384]
[626, 16384, 65536]
[2056, 65536, 262144]
[6918, 262144, 1048576]
[23714, 1048576, 4194304]
The first column is A014137, the partial sums of the Catalan numbers, which is strong support for the conjecture. The conjecture has now been proved by Raghavendra Tripathi - see link. (End)
EXAMPLE
The van der Corput sequence v(n), n >= 1, is 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16, 5/16, 13/16, 3/16, 11/16, ... = A030101/ A062383. Then we construct the sequence b(n) = v( A014486(n)), n >= 1, which is 1/4, 5/16, 3/16, 21/64, 13/64, 19/64, 11/64, 7/64, ... a(n) is the denominator of b(n), and A072800(n) is the numerator.
PROG
(PARI) \\ Program from Hugo Pfoertner for studying the connection with the Catalan numbers mentioned in the Comments. a30101(n)=fromdigits(Vecrev(binary(n)), 2);
a62383(n)=1<<(log(2*n+1)\log(2));
is_a14486(n)={my(v=binary(n), t=0); for(i=1, #v, t+=if(v[i], 1, -1); if(t<0, return(0))); t==0};
A14486=[]; for(k=1, 5000000, if(is_a14486(k), A14486=concat(A14486, k)));
aprev=0; for(k=1, #A14486, my(j=A14486[k], a=denominator(a30101(j)/a62383(j))); if(a!=aprev, print([k, aprev, a]); aprev=a));
0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 4, 1, 0, 1, 0, 0, 0, 2, 4, 6, 8, 10, 2, 5, 0, 4, 2, 2, 0, 2, 0, 0, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 4, 7, 10, 13, 0, 4, 8, 12, 4, 9, 4, 1, 0, 1, 4, 4, 0, 1, 0, 0, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42
PROG
(C) int A062383(int n) { if(n==0) return 1; return 2*( A062383(n/2)); } int a(int n) { return n % ( A062383(n)-n); } (PARI) b(n) = if (n, 2*b(n\2), 1);
(Python)
AUTHOR
J. Z. Bradley (jzbradley(AT)gmail.com), Dec 29 2008
Binary order of n: log_2(n) rounded up to next integer.
+10
262
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
COMMENTS
Or, ceiling(log_2(n)).
Worst-case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1). Let x(0) = n > 1 and x(k + 1) = x(k) - floor(x(k)/2), then a(n) is the smallest integer such that x(a(n)) = 1. - Benoit Cloitre, Aug 29 2002 Also number of division steps when going from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard, Mar 25 2003 Number of ways to write n as (x + 2^y), x >= 0. Number of ways to write n + 1 as 2^x + 3^y (cf. A004050). - Benoit Cloitre, Mar 29 2003 The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.
FORMULA
a(n) = ceiling(log_2(n)).
a(1) = 0; for n > 1, a(2n) = a(n) + 1, a(2n + 1) = a(n) + 1. Alternatively, a(1) = 0; for n > 1, a(n) = a(ceiling(n/2)) + 1. [corrected by Ilya Gutkovskiy, Mar 21 2020] a(n) = k such that n^(1/k - 1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k - 1) < n < 2^k. - Amarnath Murthy, May 06 2001 G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - Ralf Stephan, Apr 13 2002 a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
EXAMPLE
a(1) = 0, since log_2(1) = 0.
a(2) = 1, since log_2(2) = 1.
a(3) = 2, since log_2(3) = 1.58...
a(n) = 7 for n = 65, 66, ..., 127, 128.
G.f. = x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + ... - Michael Somos, Jun 02 2019
MAPLE
a:= n-> (p-> p+`if`(2^p<n, 1, 0))(ilog2(n)):
MATHEMATICA
Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* Peter Luschny, Dec 02 2017 *) a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* Michael Somos, Jul 10 2018 *)
PROG
(PARI) {a(n) = if( n<1, 0, ceil(log(n) / log(2)))};
(PARI) /* Set p = 1, then: */
xpcount(n, p) = for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0, p1/=2; ct++, p1 = p1*p+1)); print1(ct, ", "))
(PARI) {a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */ (Haskell)
a029837 n = a029837_list !! (n-1)
a029837_list = scanl1 (+) a209229_list
(Scala) (1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020 (Python)
s = bin(n)[2:]
return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020 (Python)
a(n) is the number produced when n is converted to binary digits, the binary digits are reversed and then converted back into a decimal number.
+10
193
0, 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 13, 3, 11, 7, 15, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19, 51, 11, 43, 27, 59, 7, 39, 23, 55, 15, 47, 31, 63, 1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57
COMMENTS
As with decimal reversal, initial zeros are ignored; otherwise, the reverse of 1 would be 1000000... ad infinitum.
Numerators of the binary van der Corput sequence. - Eric Rowland, Feb 12 2008 The number of occasions A030101(n) = A000265(n) before n = 2^k is A053599(k) + 1. For n = 0..2^19, the sequences match less than 1% of the time. - Andrew Woods, May 19 2012 Given any n > 1, the set of numbers A030109(i) = ( A030101(i) - 1)/2 for indexes i ranging from 2^n to 2^(n + 1) - 1 is a permutation of the set of consecutive integers {0, 1, 2, ..., 2^n - 1}. This is important in the standard FFT algorithms (starting or ending bit-reversal permutation). - Stanislav Sykora, Mar 15 2012 The binary van der Corput sequence is the infinite sequence of fractions { A030101(n)/ A062383(n), n = 0, 1, 2, 3, ... }, and begins 0, 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16, 5/16, 13/16, 3/16, 11/16, 7/16, 15/16, 1/32, 17/32, 9/32, 25/32, 5/32, 21/32, 13/32, 29/32, 3/32, 19/32, 11/32, 27/32, 7/32, 23/32, 15/32, 31/32, 1/64, 33/64, 17/64, 49/64, ... - N. J. A. Sloane, Dec 01 2019
REFERENCES
Hlawka E. The theory of uniform distribution. Academic Publishers, Berkhamsted, 1984. See pp. 93, 94 for the van der Corput sequence. - N. J. A. Sloane, Dec 01 2019
FORMULA
a(n) = 0, a(2n) = a(n), a(2n+1) = a(n) + 2^(floor(log_2(n)) + 1). For n > 0, a(n) = 2* A030109(n) - 1. - Ralf Stephan, Sep 15 2003 a(n) = b(n, 0) with b(n, r) = r if n = 0, otherwise b(floor(n/2), 2*r + n mod 2). - Reinhard Zumkeller, Mar 03 2010 a(1) = 1, a(3) = 3, a(2n) = a(n), a(4n+1) = 2a(2n+1) - a(n), a(4n+3) = 3a(2n+1) - 2a(n) (as in the Project Euler problem). To prove this, expand the recurrence into binary strings and reversals. - David Applegate, Mar 16 2014, following a posting to the Sequence Fans Mailing List by Martin Møller Skarbiniks Pedersen.
EXAMPLE
a(100) = 19 because 100 (base 10) = 1100100 (base 2) and R(1100100 (base 2)) = 10011 (base 2) = 19 (base 10).
MAPLE
convert(n, base, 2) ;
ListTools[Reverse](%) ;
add(op(i, %)*2^(i-1), i=1..nops(%)) ;
# second Maple program:
a:= proc(n) local m, r; m:=n; r:=0;
while m>0 do r:=r*2+irem(m, 2, 'm') od; r
end:
MATHEMATICA
Table[FromDigits[Reverse[IntegerDigits[i, 2]], 2], {i, 0, 80}]
bitRev[n_] := Switch[Mod[n, 4], 0, bitRev[n/2], 1, 2 bitRev[(n + 1)/2] - bitRev[(n - 1)/4], 2, bitRev[n/2], 3, 3 bitRev[(n - 1)/2] - 2 bitRev[(n - 3)/4]]; bitRev[0] = 0; bitRev[1] = 1; bitRev[3] = 3; Array[bitRev, 80, 0] (* Robert G. Wilson v, Mar 18 2014 *)
PROG
(PARI) a(n)=if(n<1, 0, subst(Polrev(binary(n)), x, 2))
(PARI) a(n) = fromdigits(Vecrev(binary(n)), 2); \\ Michel Marcus, Nov 10 2017 (Magma) A030101:=func<n|SequenceToInteger(Reverse(IntegerToSequence(n, 2)), 2)>; // Jason Kimberley, Sep 19 2011 (Haskell)
a030101 = f 0 where
f y 0 = y
f y x = f (2 * y + b) x' where (x', b) = divMod x 2
(Sage)
def A030101(n): return Integer(bin(n).lstrip("0b")[::-1], 2) if n!=0 else 0 (Python)
def a(n): return int(bin(n)[2:][::-1], 2) # Indranil Ghosh, Apr 24 2017 (Scala) (0 to 127).map(n => Integer.parseInt(Integer.toString(n, 2).reverse, 2)) // Alonso del Arte, Feb 11 2020
Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.
+10
117
0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64
COMMENTS
Except for the initial term, 2^n appears 2^n times. - Lekraj Beedassy, May 26 2005 a(n) is the sum of totient function over powers of 2 <= n. - Anthony Browne, Jun 17 2016 Given positive n, reverse the bits of n and divide by 2^floor(log_2 n). Numerators are in A030101. Ignoring the initial 0, denominators are in this sequence. - Alonso del Arte, Feb 11 2020
FORMULA
a(n) = a(floor(n / 2)) * 2.
a(0) = 0, a(1) = 1 and a(n+1) = a(n)*floor(n/a(n)). - Benoit Cloitre, Aug 17 2002 G.f.: 1/(1 - x) * (x + Sum_{k >= 1} 2^(k - 1)*x^2^k). - Ralf Stephan, Apr 18 2003
MATHEMATICA
nv[n_] := Module[{c = 2^n}, Table[c, {c}]]; Join[{0}, Flatten[Array[nv, 7, 0]]] (* Harvey P. Dale, Jul 17 2012 *)
PROG
(Haskell)
a053644 n = if n <= 1 then n else 2 * a053644 (div n 2)
a053644_list = 0 : concat (iterate (\zs -> map (* 2) (zs ++ zs)) [1])
(PARI) a(n) = if(!n, 0, 2^exponent(n)) \\ Iain Fox, Dec 10 2018 (Python)
def a(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1) # Indranil Ghosh, May 25 2017 (Scala) (0 to 127).map(Integer.highestOneBit(_)) // Alonso del Arte, Feb 26 2020 (Python)
CROSSREFS
See A000035 for least significant bit(n). MASKTRANS transform of A055975 (prepended with 0), MASKTRANSi transform of A048678. This is Guy Steele's sequence GS(5, 5) (see A135416).
Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.
(Formerly M2216)
+10
103
0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29
COMMENTS
Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.
A version of the children's game "One potato, two potato, ...".
a(n)/ A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006 By inspection, the solution to the Josephus Problem is a sequence of odd numbers (from 1) starting at each power of 2. This yields a direct closed form expression (see formula below). - Gregory Pat Scandalis, Oct 15 2013 Also zero together with a triangle read by rows in which row n lists the first 2^(n-1) odd numbers (see A005408), n >= 1. Row lengths give A011782. Right border gives A000225. Row sums give A000302, n >= 1. See example. - Omar E. Pol, Oct 16 2013 In binary, a(n) = ROL(n), where ROL = rotate left = remove the leftmost digit and append it to the right. For example, n = 41 = 101001_2 => a(n) = (0)10011_2 = 19. This also explains FTAW's comment above. - M. F. Hasler, Nov 02 2016 In the under-down Australian card deck separation: top card on bottom of a deck of n cards, next card separated on the table, etc., until one card is left. The position a(n), for n >= 1, from top will be the left over card. See, e.g., the Behrends reference, pp. 156-164. For the down-under case see 2* A053645(n), for n >= 3, n not a power of 2. If n >= 2 is a power of 2 the botton card survives. - Wolfdieter Lang, Jul 28 2020
REFERENCES
Erhard Behrends, Der mathematische Zauberstab, Rowolth Taschenbuch Verlag, rororo 62902, 4. Auflage, 2019, pp. 156-164. [English version: The Math Behind the Magic, AMS, 2019.]
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.
M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc. (AMS), 2009.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Paul Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.
FORMULA
To get a(n), write n in binary, rotate left 1 place.
G.f.: 1 + 2/(1-x) * ((3*x-1)/(2-2*x) - Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003 a(n) = number of positive integers k < n such that n XOR k < n. a(n) = n - A035327(n). - Paul D. Hanna, Jan 21 2006 a(n) = n for n = 2^k - 1. - Zak Seidov, Dec 14 2006 a(2^m+k) = 1+2*k; with 0 <= m and 0 <= k < 2^m; n = 2^m+k; m = floor(log_2(n)); k = n-2^m; a(n) = ((a(n-1)+1) mod n) + 1; a(1) = 1. E.g., n=27; m=4; k=11; a(27) = 1 + 2*11 = 23. - Paul Weisenhorn, Oct 10 2010 a(n) = 0 if n = 0 and a(n) = 2*a(floor(n/2)) - (-1)^(n mod 2) if n > 0. - Marek A. Suchenek, Mar 31 2016 G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - Ilya Gutkovskiy, Aug 31 2019
EXAMPLE
Written as an irregular triangle the sequence begins:
0;
1;
1,3;
1,3,5,7;
1,3,5,7,9,11,13,15;
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,
43,45,47,49,51,53,55,57,59,61,63;
...
(End)
An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:
n a(n) Diagram
0 0 _
1 1 |_|_ _
2 1 |_| |
3 3 |_ _|_ _ _ _
4 1 |_| | | |
5 3 |_ _| | |
6 5 |_ _ _| |
7 7 |_ _ _ _|
(End)
MAPLE
a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:
convert(n, base, 2) ;
ListTools[Rotate](%, -1) ;
add( op(i, %)*2^(i-1), i=1..nops(%)) ;
A006257 := n -> 2*n - Bits:-Iff(n, n):
MATHEMATICA
Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v, Sep 21 2003 *) Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy, Feb 07 2011 *) m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy, Feb 07 2011 *)
PROG
(PARI) a(n)=sum(k=1, n, if(bitxor(n, k)<n, 1, 0)) \\ Paul D. Hanna(Haskell)
a006257 n = a006257_list !! n
a006257_list =
0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])
(Magma) [0] cat [2*(n-2^Floor(Log(2, n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016 (Python)
import math
return 0 if n==0 else 2*(n-2**int(math.log(n, 2)))+1 # Indranil Ghosh, Jan 11 2017 (Python)
def A006257(n): return bool(n&(m:=1<<n.bit_length()-1))+((n&m-1)<<1) if n else 0 # Chai Wah Wu, Jan 22 2023 (C#)
(Coq)
Require Import ZArith.
Fixpoint a (n : positive) : Z :=
match n with
| xH => 1
| xI n' => (2*(a n') + 1)%Z
| xO n' => (2*(a n') - 1)%Z
end.
CROSSREFS
Second column, and main diagonal, of triangle A032434.
Let k be the exponent of highest power of 2 dividing n ( A007814); a(n) = 2^(k+1)-1.
+10
65
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
COMMENTS
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 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
FORMULA
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 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)
Dirichlet g.f.: zeta(s)/(1 - 2^(1-s)). - R. J. Mathar, Mar 10 2011 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) = 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
EXAMPLE
a(6) = 3 because 110 XOR 101 = 11 base 2 = 3.
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)
MAPLE
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):
MATHEMATICA
Table[Denominator[DivisorSigma[1, 2*n]/DivisorSigma[1, n]], {n, 1, 128}]
PROG
(C) int a(int n) { return n ^ (n-1); } // Russ Cox, May 15 2007 (Haskell)
import Data.Bits (xor)
(Python)
CROSSREFS
A038713 translated from binary, diagonals of A003987 on either side of main diagonal.
a(n)-1 is exponent of 2 in A089893(n). This is Guy Steele's sequence GS(6, 2) (see A135416).
Numbers whose base-2 representation is the juxtaposition of two identical strings.
+10
38
3, 10, 15, 36, 45, 54, 63, 136, 153, 170, 187, 204, 221, 238, 255, 528, 561, 594, 627, 660, 693, 726, 759, 792, 825, 858, 891, 924, 957, 990, 1023, 2080, 2145, 2210, 2275, 2340, 2405, 2470, 2535, 2600, 2665, 2730, 2795, 2860, 2925, 2990, 3055, 3120, 3185, 3250
LINKS
Daniel M. Kane, Carlo Sanna, and Jeffrey Shallit, Waring's Theorem for Binary Powers, Combinatorica, Vol. 39, No. 6 (2019), pp. 1335-1350, arXiv preprint, arXiv:1801.04483 [math.NT], 2018.
FORMULA
a(n) = n + 2*n*2^floor(log_2(n)). - Ralf Stephan, Dec 07 2004
EXAMPLE
36 is a term because 36 = 100100_2, which is 100 followed by 100.
MAPLE
a:= n-> (l-> Bits[Join]([l[], l[]]))(Bits[Split](n)):
MATHEMATICA
Table[n + 2 n 2^Floor[Log[2, n]], {n, 50}] (* T. D. Noe, Dec 10 2013 *) FromDigits[#, 2] & /@ (# <> # & /@ IntegerString[Range@100, 2]) (* Hans Rudolf Widmer, Aug 24 2024 *)
PROG
(Haskell)
a020330 n = foldr (\d v -> 2 * v + d) 0 (bs ++ bs) where
bs = a030308_row n
(Python)
def a(n): return int(bin(n)[2:]*2, 2)
(Python)
Numbers n such that BCR(n) = n, where BCR = binary-complement-and-reverse = take one's complement then reverse bit order.
+10
34
2, 10, 12, 38, 42, 52, 56, 142, 150, 170, 178, 204, 212, 232, 240, 542, 558, 598, 614, 666, 682, 722, 738, 796, 812, 852, 868, 920, 936, 976, 992, 2110, 2142, 2222, 2254, 2358, 2390, 2470, 2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132, 3164, 3244
COMMENTS
Numbers n such that A036044(n) = n. Also: numbers such that n+BR(n) is in A000225={2^k-1} (with BR = binary reversed). - M. F. Hasler, Dec 17 2007
FORMULA
If offset were 0, a(2n+1) - a(2n) = 2^floor(log_2(n)+1).
EXAMPLE
38 is such a number because 38=100110; complement to get 011001, then reverse bit order to get 100110.
MAPLE
[seq(ReflectBinSeq(j, (floor_log_2(j)+1)), j=1..256)];
ReflectBinSeq := (x, n) -> (((2^n)*x)+binrevcompl(x));
binrevcompl := proc(nn) local n, z; n := nn; z := 0; while(n <> 0) do z := 2*z + ((n+1) mod 2); n := floor(n/2); od; RETURN(z); end;
floor_log_2 := proc(n) local nn, i: nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi: nn := floor(nn/2); od: end; # Computes essentially the same as floor(log[2](n))
# alternative Maple program:
q:= n-> (l-> is(n=add((1-l[-i])*2^(i-1), i=1..nops(l))))(Bits[Split](n)):
MATHEMATICA
bcrQ[n_]:=Module[{idn2=IntegerDigits[n, 2]}, Reverse[idn2/.{1->0, 0->1}] == idn2]; Select[Range[3200], bcrQ] (* Harvey P. Dale, May 24 2012 *)
PROG
(PARI) for(n=1, 1000, l=length(binary(n)); b=binary(n); if(sum(i=1, l, abs(component(b, i)-component(b, l+1-i)))==l, print1(n, ", ")))
(PARI) for(i=1, 999, if(Set(vecextract(t=binary(i), "-1..1")+t)==[1], print1(i", "))) \\ M. F. Hasler, Dec 17 2007 (PARI) a(n) = my (b=binary(n)); (n+1)*2^#b-fromdigits(Vecrev(b), 2)-1 \\ Rémy Sigrist, Mar 15 2021 (Haskell)
a035928 n = a035928_list !! (n-1)
a035928_list = filter (\x -> a036044 x == x) [0, 2..]
(Python)
def comp(s): z, o = ord('0'), ord('1'); return s.translate({z:o, o:z})
def BCR(n): return int(comp(bin(n)[2:])[::-1], 2)
def aupto(limit): return [m for m in range(limit+1) if BCR(m) == m]
(Python)
from itertools import count, islice
def A035928_gen(startvalue=1): # generator of terms >= startvalue return filter(lambda n:n==int(format(~n&(1<<(m:=n.bit_length()))-1, '0'+str(m)+'b')[::-1], 2), count(max(startvalue, 1)))
a(0) = 0, a(n) = a(n-1) OR n.
+10
28
0, 1, 3, 3, 7, 7, 7, 7, 15, 15, 15, 15, 15, 15, 15, 15, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63
COMMENTS
Also, 0+1+2+...+n in lunar arithmetic in base 2 written in base 10. - N. J. A. Sloane, Oct 02 2010 For n>0: replace all 0's with 1's in binary representation of n. - Reinhard Zumkeller, Jul 14 2003
LINKS
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
FORMULA
a(n) = a(n-1) + n*(1-floor(a(n-1)/n)). If 2^(k-1) <= n < 2^k, a(n) = 2^k - 1. - Benoit Cloitre, Aug 25 2002 G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k. - Ralf Stephan, Apr 18 2003 G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 - x). - Ilya Gutkovskiy, Aug 31 2019
MAPLE
A003817 := n -> n + Bits:-Nand(n, n):
MATHEMATICA
a[0] = 0; a[n_] := a[n] = BitOr[ a[n-1], n]; Table[a[n], {n, 0, 61}] (* Jean-François Alcover, Dec 19 2011 *) nxt[{n_, a_}]:={n+1, BitOr[a, n+1]}; Transpose[NestList[nxt, {0, 0}, 70]] [[2]] (* Harvey P. Dale, May 06 2016 *) 2^BitLength[Range[0, 100]]-1 (* Paolo Xausa, Feb 08 2024 *)
PROG
(Haskell)
import Data.Bits ((.|.))
a003817 n = if n == 0 then 0 else 2 * a053644 n - 1
a003817_list = scanl (.|.) 0 [1..] :: [Integer]
(Python)
def a(n): return 0 if n==0 else 1 + 2*a(int(n/2)) # Indranil Ghosh, Apr 28 2017 (Python)
CROSSREFS
This is Guy Steele's sequence GS(6, 6) (see A135416).
Search completed in 0.040 seconds
|