This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
a(4) = 2 since 4 in binary is 100, which has two zeros. a(5) = 1 since 5 in binary is 101, which has only one zero.
seq(numboccur(0, Bits[Split](n)), n=0..100); # Robert Israel, Oct 26 2017
{0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* Michael De Vlieger, Mar 07 2016 *)
f[n_] := If[OddQ@ n, f[n -1] -1, f[n/2] +1]; f[0] = f[1] = 0; Array[f, 105, 0] (* Robert G. Wilson v, May 21 2017 *)
Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* Vincenzo Librandi, Oct 27 2017 *)
a(n)=if(n,a(n\2)+1-n%2)
A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ M. F. Hasler, Oct 26 2017
def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017
;; with memoizing definec-macro from Antti Karttunen's IntSeq-library) (define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n))) ;; Alternative version based on a simple recurrence: (definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1))) ;; from Antti Karttunen, Dec 12 2013
a[0] = 0; a[n_] := a[n] = If[n == 1, 1, # + 1 + Last@ DigitCount[#, 2] &@ a[n - 1]]; Table[a@ n, {n, 0, 59}] (* or *)
Insert[NestList[# + 1 + DigitCount[#, 2, 0] &, 0, nn], 1, 2] (* Michael De Vlieger, Mar 07 2016, the latter after Harvey P. Dale at A216431 *)
We consider 0 to have no nonleading zeros, so first we get to 0 -> 0+1+0 = 1, and 1 is odd, so we go one step down from the starting value a(0)=0, and thus a(1) = -1. 1 has no nonleading zeros, so we get 1 -> 1+1+0 = 2, and 2 is even, so we go one step up, and thus a(2) = 0. 2 has one nonleading zero in binary "10", so we get 2 -> 2+1+1 = 4, and 4 is also even, so we go one step up, and thus a(3) = 1. 4 has two nonleading zeros in binary "100", so we get 4 -> 4+2+1 = 7, 7 is odd, so we go one step down, and thus a(4) = 0.
A070939 = n->#binary(n)+!n; \\ From M. F. Hasler A080791 = n->if(n<1,0,(A070939(n)-hammingweight(n))); A233272 = n->(n + A080791(n) + 1); A257806_write_bfile(up_to_n) = { my(n,a_n=0,b_n=0); for(n=0, up_to_n, write("b257806.txt", n, " ", a_n); b_n = A233272(b_n); a_n += ((-1)^b_n)); }; A257806_write_bfile(8727);
def A257806_print_upto(n): a = 0 b = 0 for n in range(n): print(b, end=", ") ta = a c0 = 0 while ta>0: c0 += 1-(ta&1) ta >>= 1 a += 1 + c0 b += ((2*(1-(a&1))) - 1) # By Antti Karttunen after Alex Ratushnyak's Python-code for A216431.
(define (A257806 n) (- (A257808 n) (A257807 n)))
;; Using memoizing definec-macro. (definec (A257806 n) (if (zero? n) n (+ (expt -1 (A233271 n)) (A257806 (- n 1)))))
NestList[#+1+DigitCount[#,2,0]&,0,60] (* Harvey P. Dale, Sep 25 2013 *)
a = 0
for n in range(100):
print(a, end=', ')
ta = a
c0 = (a==0)
while ta>0:
c0 += 1-(ta&1)
ta >>= 1
a += 1 + c0
;; With memoizing definec-macro from Antti Karttunen's IntSeq-library. (definec (A216431 n) (if (< n 2) (+ n n) (A233272 (A216431 (- n 1))))) ;; Antti Karttunen, Dec 12 2013
(define (A234018 n) (A233270 (A233268 n))) ;; Iterative version, which computes for values a(n>=4) in a single pass: (define (A234018v2 n) (cond ((zero? n) 0) ((< n 4) (A234018 n)) (else (let* ((memosize (if (< n 8) 2 (+ 2 (expt 2 (- n 8))))) (memo (make-vector memosize 0))) (let loop ((u (- (A000079 n) 1)) (d (A000079 (- n 1))) (i 0) (j #f) (du #f)) (cond ((pow2? u) (let ((offset (- (floor->exact (/ i 2)) du))) (- (A054429 (vector-ref memo offset)) (vector-ref memo (+ offset (A000035 i)))))) ((and (< u d) (not j)) (vector-set! memo 0 u) (loop (A011371 u) (A233272 d) (+ i 1) 1 i)) (else (if (and j (< j memosize)) (vector-set! memo j u)) (loop (A011371 u) (A233272 d) (+ i 1) (and j (+ 1 j)) du)))))))) (define (pow2? n) (let loop ((n n) (i 0)) (cond ((zero? n) #f) ((odd? n) (and (= 1 n) i)) (else (loop (/ n 2) (1+ i))))))
s = Range[2^(# + 1) - 1, 2^#, -1] & /@ Range[0, 12] // Flatten; t = Complement[#, 2 # - DigitCount[2 #, 2, 1] & /@ #] &@ Range[20007]; Table[s[[ t[[ s[[n]] ]] ]], {n, 74}] (* Michael De Vlieger, Jun 01 2016, after Harvey P. Dale at A005187 and A054429 *)
(define (A270198 n) (A054429 (A055938 (A054429 n))))
s = Range[2^(# + 1) - 1, 2^#, -1] & /@ Range[0, 12] // Flatten; {0, 1}~Join~Table[s[[2 # - DigitCount[2 #, 2, 1] &[1 + s[[n - 1]]]]], {n, 2, 74}] (* Michael De Vlieger, Jun 01 2016, after Harvey P. Dale at A005187 and A054429 *)
For n = 10 a(10) = 2037 because:
Size | Block pair (l,m)(m,r) to merge | Left over block | Encoding
-----+--------------------------------+------------------+-----------
1 | ((0, 0), (0, 1)) | | 1
1 | ((2, 2), (2, 3)) | | 11
1 | ((4, 4), (4, 5)) | | 111
1 | ((6, 6), (6, 7)) | | 1111
1 | ((8, 8), (8, 9)) | | 11111
2 | ((0, 1), (1, 3)) | | 111111
2 | ((4, 5), (5, 7)) | | 1111111
2 | | ((8, 9), (9, 9)) | 11111110
4 | ((0, 3), (3, 7)) | | 111111101
4 | | ((8, 9), (9, 9)) | 1111111010
8 | ((0, 7), (7, 9)) | | 11111110101
11111110101 in base 10 is 2037.
For n=10, the merges performed on 1,...,10 begin with pairs of "blocks" of length 1 each,
1 2 3 4 5 6 7 8 9 10
\--/ \--/ \--/ \--/ \---/
1 1 1 1 1 encoding
[1 2] [3 4] [5 6] [7 8] [9 10]
\---------/ \---------/
1 1 0 encoding
Similarly on the resulting 3 blocks
[1 2 3 4] [5 6 7 8] [9 10]
\-----------------/
1 0 encoding
Then a merge of the resulting 2 blocks to a single sorted block.
[1 2 3 4 5 6 7 8] [9 10]
\----------------------/
1 encoding
These encodings are then a(10) = binary 11111 110 10 1 = 2037.
def a(n):
if n == 1: return 0
s, t, n1 = 1, 0, (n - 1)
while s < n:
d = s << 1
for l in range(0, n, d):
m,r = min(l - 1 + s, n1), min(l - 1 + d, n1)
t = (t << 1) + int(m < r)
s = d
return t
print([a(n) for n in range (1,22)])
Comments