Displaying 1-10 of 20 results found.
a(0) = 0, after which a(n) gives the total number of runs of the same length as the rightmost run in the binary representation of a(n-1) [i.e., A136480(a(n-1))] among the binary expansions of all previous terms, including the runs in a(n-1) itself.
+20
5
0, 1, 2, 4, 1, 6, 7, 1, 8, 2, 11, 3, 4, 5, 17, 19, 7, 4, 8, 5, 25, 26, 29, 31, 1, 32, 2, 35, 12, 14, 37, 41, 45, 49, 50, 52, 22, 57, 58, 61, 63, 1, 64, 2, 67, 25, 69, 73, 76, 32, 3, 33, 80, 4, 34, 87, 14, 92, 35, 36, 38, 99, 42, 105, 108, 47, 5, 114, 116, 49, 119, 23, 24, 25, 123, 54, 126, 127, 1, 128, 2
EXAMPLE
a(0) = 0 (by definition), and 0 is also '0' in binary.
For n = 1, we see that in a(0) there is one run of length 1, which is total number of runs of length 1 so far in terms a(0) .. a(n-1), thus a(1) = 1.
For n = 2, we see that the rightmost run of a(1) = 1 ('1' also in binary) has occurred two times in total (once in a(0) and a(1)), thus a(2) = 2.
For n = 3, we see that the rightmost run of a(2) = 2 ('10' in binary) is one bit long, and so far there has occurred four such runs in total (namely once in a(0) and a(1), twice in a(2)), thus a(3) = 4.
For n = 4, we see that the rightmost run of a(3) = 4 ('100' in binary) is two bits long, and it is so far the first and only two-bit run in the sequence, thus a(4) = 1.
For n = 5, we see that the rightmost run of a(4) = 1 ('1' in binary) is one bit long, and so far there has occurred 6 such one-bit runs in terms a(0) .. a(4), thus a(5) = 6.
For n = 6, we see that the rightmost run of a(5) = 6 ('110' in binary) is one bit long, and so far there has occurred 7 such one bit runs in terms a(0) .. a(5), thus a(6) = 7.
PROG
(MIT/GNU Scheme with memoizing definec-macro from Antti Karttunen's IntSeq-library) ;; For binexp->runcount1list see for example A129594. (definec ( A249144 n) (if (< n 2) n (vector-ref (A249144aux_runlen_counts (- n 1)) (-1+ ( A136480 ( A249144 (- n 1))))))) (definec (A249144aux_runlen_counts n) (cond ((zero? n) (vector 1)) (else (let* ((a_n ( A249144 n)) (copy-of-prevec (vector-copy (A249144aux_runlen_counts (- n 1)))) (newsize (max (vector-length copy-of-prevec) ( A043276 a_n))) (lencounts-for-n (vector-grow copy-of-prevec newsize))) (let loop ((runlens (binexp->runcount1list a_n))) (cond ((null? runlens) lencounts-for-n) (else (vector-set! lencounts-for-n (- (car runlens) 1) (+ 1 (or (vector-ref lencounts-for-n (- (car runlens) 1)) 0))) (loop (cdr runlens)))))))))
1, 1, 2, 1, 1, 3, 1, 3, 1, 2, 2, 2, 1, 1, 2, 3, 2, 3, 1, 1, 1, 1, 5, 1, 5, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 6, 1, 2, 1, 1, 1, 2, 5, 2, 1, 4, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 3, 3, 3, 1, 2, 1, 1, 7, 1, 7, 1, 2, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 6, 2, 2, 4, 2, 1, 1, 1, 4, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 3, 3, 3, 1, 1, 2, 2, 1
Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.
+10
930
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
COMMENTS
This sequence is an exception to my usual rule that when every other term of a sequence is 0 then those 0's should be omitted. In this case we would get A001511. - N. J. A. SloaneTo construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc. - Benoit Cloitre, Mar 06 2003 The sequence is invariant under the following two transformations: increment every element by one (1, 2, 1, 3, 1, 2, 1, 4, ...), put a zero in front and between adjacent elements (0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...). The intermediate result is A001511. - Ralf Hinze (ralf(AT)informatik.uni-bonn.de), Aug 26 2003 Fixed point of the morphism 0->01, 1->02, 2->03, 3->04, ..., n->0(n+1), ..., starting from a(1) = 0. - Philippe Deléham, Mar 15 2004 Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - Joerg Arndt, Apr 29 2014 a(n) is also the number of times to repeat a step on an even number in the hailstone sequence referenced in the Collatz conjecture. - Alex T. Flood (whiteangelsgrace(AT)gmail.com), Sep 22 2006
Let F(n) be the n-th Fermat number ( A000215). Then F(a(r-1)) divides F(n)+2^k for r = k mod 2^n and r != 1. - T. D. Noe, Jul 12 2007 The following relation holds: 2^ A007814(n)*(2* A025480(n-1)+1) = A001477(n) = n. (See functions hd, tl and cons in [Paul Tarau 2009].) a(n) is the number of 0's at the end of n when n is written in base 2.
a(n+1) is the number of 1's at the end of n when n is written in base 2. - M. F. Hasler, Aug 25 2012 Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 0). That is, A003188(n) XOR A003188(n+1) == 2^ A007814(n). - Russ Cox, Dec 04 2010 The sequence is squarefree (in the sense of not containing any subsequence of the form XX) [Allouche and Shallit]. Of course it contains individual terms that are squares (such as 4). - Comment expanded by N. J. A. Sloane, Jan 28 2019 a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - T. D. Noe, Mar 01 2011 Lemma: For n < m with r = a(n) = a(m) there exists n < k < m with a(k) > r. Proof: We have n=b2^r and m=c2^r with b < c both odd; choose an even i between them; now a(i2^r) > r and n < i2^r < m. QED. Corollary: Every finite run of consecutive integers has a unique maximum 2-adic valuation. - Jason Kimberley, Sep 09 2011 a(n) = number of 1's in the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} p_j-th prime (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24)=3; indeed, the partition having Heinz number 24 = 2*2*2*3 is [1,1,1,2]. - Emeric Deutsch, Jun 04 2015 a(n+1) is the difference between the two largest parts in the integer partition having viabin number n (0 is assumed to be a part). Example: a(20) = 2. Indeed, we have 19 = 10011_2, leading to the Ferrers board of the partition [3,1,1]. For the definition of viabin number see the comment in A290253. - Emeric Deutsch, Aug 24 2017 Apart from being squarefree, as noted above, the sequence has the property that every consecutive subsequence contains at least one number an odd number of times. - Jon Richfield, Dec 20 2018 a(n+1) is the 2-adic valuation of Sum_{e=0..n} u^e = (1 + u + u^2 + ... + u^n), for any u of the form 4k+1 ( A016813). - Antti Karttunen, Aug 15 2020 {a(n)} represents the "first black hat" strategy for the game of countably infinitely many hats, with a probability of success of 1/3; cf. the Numberphile link below. - Frederic Ruget, Jun 14 2021
REFERENCES
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.
K. Atanassov, On the 37th and the 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
LINKS
Giovanni Pighizzini, Limited Automata: Properties, Complexity and Variants, International Conference on Descriptional Complexity of Formal Systems (DCFS 2019) Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science (LNCS, Vol. 11612) Springer, Cham, 57-73.
FORMULA
G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Apr 10 2002 Totally additive with a(p) = 1 if p = 2, 0 otherwise.
Dirichlet g.f.: zeta(s)/(2^s-1). - Ralf Stephan, Jun 17 2007 Define 0 <= k <= 2^n - 1; binary: k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1); where b(x) are 0 or 1 for 0 <= x <= n - 1; define c(x) = 1 - b(x) for 0 <= x <= n - 1; Then: a(k) = c(0) + c(0)*c(1) + c(0)*c(1)*c(2) + ... + c(0)*c(1)...c(n-1); a(k+1) = b(0) + b(0)*b(1) + b(0)*b(1)*b(2) + ... + b(0)*b(1)...b(n-1). - Arie Werksma (werksma(AT)tiscali.nl), May 10 2008
v_{2}(n) = Sum_{r>=1} (r / 2^(r+1)) Sum_{k=0..2^(r+1)-1} e^(2(k*Pi*i(n+2^r))/(2^(r+1))). - A. Neves, Sep 28 2010, corrected Oct 04 2010 a(n)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Feb 16 2019 Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - Amiram Eldar, Jul 11 2020 a(n) = 2*Sum_{j=1..floor(log_2(n))} frac(binomial(n, 2^j)*2^(j-1)/n). - Dario T. de Castro, Jul 08 2022 a(n) = floor((gcd(n, 2^n)^(n+1) mod (2^(n+1)-1)^2)/(2^(n+1)-1)) (see Lemma 3.4 from Mazzanti's 2002 article). - Lorenzo Sauras Altuzarra, Mar 10 2024
EXAMPLE
2^3 divides 24, so a(24)=3.
Triangle begins:
0;
1,0;
2,0,1,0;
3,0,1,0,2,0,1,0;
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,...
(End)
MAPLE
ord := proc(n) local i, j; if n=0 then return 0; fi; i:=0; j:=n; while j mod 2 <> 1 do i:=i+1; j:=j/2; od: i; end proc: seq(ord(n), n=1..111);
MATHEMATICA
p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]
DigitCount[BitXor[x, x - 1], 2, 1] - 1; a different version based on the same concept: Floor[Log[2, BitXor[x, x - 1]]] (* Jaume Simon Gispert (jaume(AT)nuem.com), Aug 29 2004 *)
Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)
Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 17 2011 *)
PROG
(Haskell)
a007814 n = if m == 0 then 1 + a007814 n' else 0
where (n', m) = divMod n 2
(Haskell)
a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)
(Magma) [Valuation(n, 2): n in [1..120]]; // Bruno Berselli, Aug 05 2013 (Python)
import math
def a(n): return int(math.log(n - (n & n - 1), 2)) # Indranil Ghosh, Apr 18 2017 (Python)
(Scheme) (define ( A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017
a(n) is the sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n; row sums of A227739 for n >= 1.
+10
23
0, 1, 2, 2, 4, 3, 3, 3, 6, 5, 4, 6, 5, 4, 4, 4, 8, 7, 6, 8, 8, 5, 7, 9, 7, 6, 5, 7, 6, 5, 5, 5, 10, 9, 8, 10, 10, 7, 9, 11, 12, 9, 6, 10, 11, 8, 10, 12, 9, 8, 7, 9, 9, 6, 8, 10, 8, 7, 6, 8, 7, 6, 6, 6, 12, 11, 10, 12, 12, 9, 11, 13, 14, 11, 8, 12, 13, 10, 12, 14
COMMENTS
Like A129594 this sequence utilizes the fact that compositions (i.e., ordered partitions) can be bijectively mapped to (unordered) partitions by taking the partial sums of the list of composants after one has been subtracted from each except the first one. Compositions in turn are mapped to nonnegative integers via the runlength encoding, where the lengths of maximum runs of 0's or 1's in binary representation of n give the composants. See the OEIS Wiki page and the example below. Each n occurs A000041(n) times in total and occurs for the first time at A227368(n) and for the last time at position A000225(n). See further comments and conjectures at A227368 and A227370.
FORMULA
Other identities:
a( A129594(n)) = a(n). [This follows from the fact that conjugating a partition doesn't change its total sum] a( A226062(n)) = a(n). [Which is also true for the "Bulgarian operation"] Can be also obtained by mapping with an appropriate permutation from the sequences giving sizes of each partition (i.e., sum of their parts) computed for other enumerations similar to A227739: (End)
EXAMPLE
19 has binary expansion "10011", thus the maximal runs of identical bits (scanned from right to left) are [2,2,1]. We subtract one from each after the first one, to get [2,1,0] and then form their partial sums as [2,2+1,2+1+0], which thus maps to unordered partition {2+3+3} which adds to 8. Thus a(19)=8.
MATHEMATICA
Table[Function[b, Total@ Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b] - Boole[n == 0]]@ Map[Length, Split@ Reverse@ IntegerDigits[n, 2]], {n, 0, 79}] // Flatten (* Michael De Vlieger, May 09 2017 *)
PROG
(definec ( A227183 n) (let loop ((n n) (i ( A005811 n)) (d 0) (s 0)) (cond ((zero? n) s) (else (loop ( A163575 n) (- i 1) (expt 1 d) (+ s (* i (- ( A136480 n) d)))))))) (define (A227183v2 n) (if (zero? n) n (apply + (binexp_to_ascpart n)))) ;; Alternative definition, using the same auxiliary functions as A227184, which are given there. (define (A227183v3 n) (let loop ((i (- ( A005811 n) 1)) (s 0)) (cond ((< i 0) s) (else (loop (- i 1) (+ s (A227189bi n i))))))) ;; Another variant which sums the nonzero terms of the row n of array A227189. ;; As well:
;; This implements Sum_{i=lowlim..uplim} intfun(i)
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))
(Python)
'''Sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n.'''
s = 0
b = n%2
i = 1
while (n != 0):
n >>= 1
if ((n%2) == b): # Staying in the same run of bits?
i += 1
else: # The run changes.
b = n%2
s += i
return(s)
Irregular table read by rows: the first entry of n-th row is length of run of rightmost identical bits (either 0 or 1, equal to n mod 2), followed by length of the next run of bits, etc., in the binary representation of n, when scanned from the least significant to the most significant end.
+10
22
1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 3, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 3, 4, 4, 1, 1, 3, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 2, 3, 1, 1, 3, 1, 4, 5, 5, 1, 1, 4, 1, 1, 1, 3, 1
COMMENTS
Row n has A005811(n) terms. In rows 2^(k-1)..2^k-1 we have all the compositions (ordered partitions) of k. Other orderings of compositions: A101211, A066099, A108244 and A124734. Each row n (n>=1) contains the initial A005811(n) nonzero terms from the beginning of row n of A227186. A070939(n) gives the sum of terms on row n, while A167489(n) gives the product of its terms. A136480 gives the first column. A101211 lists the terms of each row in reverse order.
EXAMPLE
Table begins as:
Row n in Terms on
n binary that row
1 1 1;
2 10 1,1;
3 11 2;
4 100 2,1;
5 101 1,1,1;
6 110 1,2;
7 111 3;
8 1000 3,1;
9 1001 1,2,1;
10 1010 1,1,1,1;
11 1011 2,1,1;
12 1100 2,2;
13 1101 1,1,2;
14 1110 1,3;
15 1111 4;
16 10000 4,1;
etc. with the terms of row n appearing in reverse order compared how the runs of the same length appear in the binary expansion of n (Cf. A101211). Illustration of initial terms:
---------------------------------------
k m Diagram Composition
---------------------------------------
. _
1 1 |_|_ 1;
2 1 |_| | 1, 1,
2 2 |_ _|_ 2;
3 1 |_ | | 2, 1,
3 2 |_|_| | 1, 1, 1,
3 3 |_| | 1, 2,
3 4 |_ _ _|_ 3;
4 1 |_ | | 3, 1,
4 2 |_|_ | | 1, 2, 1,
4 3 |_| | | | 1, 1, 1, 1,
4 4 |_ _|_| | 2, 1, 1,
4 5 |_ | | 2, 2,
4 6 |_|_| | 1, 1, 2,
4 7 |_| | 1, 3,
4 8 |_ _ _ _|_ 4;
5 1 |_ | | 4, 1,
5 2 |_|_ | | 1, 3, 1,
5 3 |_| | | | 1, 1, 2, 1,
5 4 |_ _|_ | | 2, 2, 1,
5 5 |_ | | | | 2, 1, 1, 1,
5 6 |_|_| | | | 1, 1, 1, 1, 1,
5 7 |_| | | | 1, 2, 1, 1,
5 8 |_ _ _|_| | 3, 1, 1,
5 9 |_ | | 3, 2,
5 10 |_|_ | | 1, 2, 2,
5 11 |_| | | | 1, 1, 1, 2,
5 12 |_ _|_| | 2, 1, 2,
5 13 |_ | | 2, 3,
5 14 |_|_| | 1, 1, 3,
5 15 |_| | 1, 4,
5 16 |_ _ _ _ _| 5;
.
Also irregular triangle read by rows in which row k lists the compositions of k, k >= 1.
Triangle begins:
[1];
[1,1], [2];
[2,1], [1,1,1], [1,2],[3];
[3,1], [1,2,1], [1,1,1,1], [2,1,1], [2,2], [1,1,2], [1,3], [4];
[4,1], [1,3,1], [1,1,2,1], [2,2,1], [2,1,1,1], [1,1,1,1,1], [1,2,1,1], [3,1,1], [3,2], [1,2,2], [1,1,1,2], [2,1,2], [2,3], [1,1,3], [1,4], [5];
(End)
MATHEMATICA
Array[Length /@ Reverse@ Split@ IntegerDigits[#, 2] &, 34] // Flatten (* Michael De Vlieger, Dec 11 2020 *)
PROG
(Haskell)
import Data.List (group)
a227736 n k = a227736_tabf !! (n-1) !! (k-1)
a227736_row n = a227736_tabf !! (n-1)
a227736_tabf = map (map length . group) $ tail a030308_tabf
CROSSREFS
Cf. A227738 and also A227739 for similar table for unordered partitions.
Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n.
+10
18
0, 1, 3, 2, 4, 7, 6, 5, 11, 12, 15, 8, 9, 14, 13, 10, 20, 27, 28, 19, 16, 31, 24, 23, 22, 25, 30, 17, 18, 29, 26, 21, 43, 52, 59, 36, 35, 60, 51, 44, 47, 48, 63, 32, 39, 56, 55, 40, 41, 54, 57, 38, 33, 62, 49, 46, 45, 50, 61, 34, 37, 58, 53, 42, 84, 107, 116, 75, 68, 123
COMMENTS
This sequence is based on the fact that compositions (i.e. ordered partitions) can be mapped 1-to-1 to partitions by taking the partial sums of the list where one is subtracted from each composant except the first. (See table A227189 where the parts for each partition are listed). The inverse process, from partitions to compositions, occurs by inserting the first (i.e. smallest) element of a partition sorted into ascending order to the front of the list obtained by adding one to the first differences of the elements.
Compositions map bijectively to nonnegative integers by assigning each run of k consecutive 1's (or 0's) in binary expansion of n with summand k in the composition.
The graph of this sequence is quite interesting.
EXAMPLE
a(8) = 11, as 8 is 1000 in binary, mapping to composition 3+1 (we scan the binary expansion from the least to the most significant end), which maps to partition 3+3, whose conjugate-partition is 2+2+2, yielding composition 2+1+1, which maps to binary 1011, 11 in decimal. a(13) = 14, as 13 is 1101 in binary, mapping to composition 1+1+2, which maps to the partition 1+1+2, whose conjugate-partition is 1+3, yielding composition 1+3, which maps to binary 1110, 14 in decimal. a(11) = 8 and a(14) = 13, as taking the conjugate of a partition is a self-inverse operation.
PROG
(MIT/GNU Scheme)
(define ( A129594 n) (if (zero? n) n (ascpart_to_binexp (conjugate-partition (binexp_to_ascpart n))))) (define (conjugate-partition ascpart) (let loop ((conjpart (list)) (ascpart ascpart)) (cond ((null? ascpart) conjpart) (else (loop (cons (length ascpart) conjpart) (delete-matching-items! (map -1+ ascpart) zero?))))))
(define (binexp_to_ascpart n) (let ((runlist (reverse! (binexp->runcount1list n)))) (PARTSUMS (cons (car runlist) (map -1+ (cdr runlist))))))
(define (ascpart_to_binexp ascpart) (runcount1list->binexp (reverse! (cons (car ascpart) (map 1+ (DIFF ascpart))))))
(define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))
(define (runcount1list->binexp lista) (let loop ((lista lista) (s 0) (state 1)) (cond ((null? lista) s) (else (loop (cdr lista) (+ (* s (expt 2 (car lista))) (* state (- (expt 2 (car lista)) 1))) (- 1 state))))))
(define (DIFF a) (map - (cdr a) (reverse! (cdr (reverse a)))))
(define (PARTSUMS a) (cdr (reverse! (fold-left (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a))))
CROSSREFS
Sequences related to partitions encoded in this way:
Cf. A227189 (parts of partitions listed on separate rows of the array). Cf. A005811 (number of parts in the partition). Cf. A136480 (for n>= 1, the smallest part).
Irregular table where row n lists in nondecreasing order the parts of unordered partition encoded in the runlengths of binary expansion of n; nonzero terms of A227189.
+10
15
1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 3, 3, 3, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 1, 3, 4, 4, 4, 1, 3, 3, 1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 2, 4, 1, 1, 3, 1, 4, 5, 5, 5, 1, 4, 4, 1, 1
COMMENTS
Row n has A005811(n) elements. Each row contains a unique (unordered) partition of some integer, and all possible partitions of finite natural numbers eventually occur. The first partition that sums to k occurs at row A227368(k) and the last at row A000225(k).
EXAMPLE
Rows are constructed as:
Row n in Runlengths With one Partial sums The row sums
n binary collected subtracted of which give to, i.e. is
from lsb- from all terms on a partition of
to msb-end except 1st that row of A227183(n) 1 "1" [1] [1] 1; 1
2 "10" [1,1] [1,0] 1, 1; 2
3 "11" [2] [2] 2; 2
4 "100" [2,1] [2,0] 2, 2; 4
5 "101" [1,1,1] [1,0,0] 1, 1, 1; 3
6 "110" [1,2] [1,1] 1, 2; 3
7 "111" [3] [3] 3; 3
8 "1000" [3,1] [3,0] 3, 3; 6
9 "1001" [1,2,1] [1,1,0] 1, 2, 2; 5
10 "1010" [1,1,1,1] [1,0,0,0] 1, 1, 1, 1; 4
11 "1011" [2,1,1] [2,0,0] 2, 2, 2; 6
12 "1100" [2,2] [2,1] 2, 3; 5
13 "1101" [1,1,2] [1,0,1] 1, 1, 2; 4
14 "1110" [1,3] [1,2] 1, 3; 4
15 "1111" [4] [4] 4; 4
16 "10000" [4,1] [4,0] 4, 4; 8
MATHEMATICA
Table[Function[b, Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b]]@ Map[Length, Split@ Reverse@ IntegerDigits[n, 2]], {n, 34}] // Flatten (* Michael De Vlieger, May 09 2017 *)
1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 5, 5, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 6, 6, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 5, 5, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4
COMMENTS
Column 2 of A050600: a(n) = add1c(n,2). Consider the Collatz (or 3x+1) problem and the iterative sequence c(k) where c(0)=n is a positive integer and c(k+1)=c(k)/2 if c(k) is even, c(k+1)=(3*c(k)+1)/2 if c(k) is odd. Then a(n) is the minimum number of iterations in order to have c(a(n)) odd if n is even or c(a(n)) even if n is odd. - Benoit Cloitre, Nov 16 2001
FORMULA
G.f.: (1+x)/x^2 * Sum(k>=1, x^(2^k)/(1-x^(2^k))). - Ralf Stephan, Apr 12 2002 Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=0..m} a(k) = 2. - Amiram Eldar, Sep 15 2022
MATHEMATICA
With[{c=Table[Position[Reverse[IntegerDigits[n, 2]], 1, 1, 1], {n, 110}]// Flatten}, Riffle[c, c]] (* Harvey P. Dale, Dec 06 2018 *)
PROG
(PARI) {a(n) = my(A); if( n<0, 0, A = sum(k=1, length( binary(n+2)) - 1, x^(2^k) / (1 - x^(2^k)), x^3 * O(x^n)); polcoeff( A * (1 + x) / x^2, n))}; /* Michael Somos, May 11 2014 */ (Python)
Remove all trailing bits equal to (n mod 2) in binary representation of n.
+10
9
0, 1, 0, 1, 2, 3, 0, 1, 4, 5, 2, 3, 6, 7, 0, 1, 8, 9, 4, 5, 10, 11, 2, 3, 12, 13, 6, 7, 14, 15, 0, 1, 16, 17, 8, 9, 18, 19, 4, 5, 20, 21, 10, 11, 22, 23, 2, 3, 24, 25, 12, 13, 26, 27, 6, 7, 28, 29, 14, 15, 30, 31, 0, 1, 32, 33, 16, 17, 34, 35, 8, 9, 36, 37, 18, 19, 38, 39, 4, 5, 40, 41, 20
COMMENTS
The original name was: "The changepoint a(n) is the first predecessor from n in a binary tree with: a(n) mod 2 <> n mod 2."
In a binary tree (node(row,col)=2^(row-1)+(col-1))
__________________________________1__________________________________
_________________2__________________________________3________________
________4_________________5________________6__________________7______
____8_______9_______10_______11_______12_______13_______14_______15__
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
any node has 2 successors and one predecessor. a(n) is the first predecessor from n (going back, step by step) with another last digit (in binary sight) as n.
The subsequences from a(2^k) to a(2^(k+1) - 1) are permutations from the natural numbers from 0 to 2^k-1.
FORMULA
a(2^n -1) = 0 and a(2^n) = 1. a(2n-1) is 2x and a(2n) is 2x+1. - Robert G. Wilson v, Jul 04 2015
EXAMPLE
a(7) = a(111_2) = 0_2 = 0 (when the rightmost and only run of bits in 7's binary representation has been shifted off, only zero remains).
a(17) = a(10001_2) = 1000_2 = 8.
a(8) = a(1000_2) = 1_2 = 1.
MATHEMATICA
f[n_] := Block[{idn = IntegerDigits[n, 2], m = Mod[n, 2]}, While[ idn[[-1]] == m, idn = Most@ idn]; FromDigits[ idn, 2]]; Array[f, 83] (* or *)
f[n_] := Block[{m = n}, If[ OddQ@ m, While[OddQ@m, m--; m /= 2], While[ EvenQ@ m, m /= 2]]; m]; Array[f, 83] (* Robert G. Wilson v, Jul 04 2015 *)
PROG
(BASIC)
FUNCTION CHANGEPOINT
INPUT n
IF EVEN(n)
WHILE EVEN(n)
n = n/2
ELSE
WHILE NOT EVEN(n)
n = (n-1)/2
OUTPUT n
(PARI) a(n) = {odd = n%2; while (n%2 == odd, n \= 2); return(n); } \\ Michel Marcus, Jun 20 2013 (Haskell)
a163575 n = f n' where
f 0 = 0
f x = if b == parity then f x' else x where (x', b) = divMod x 2
(n', parity) = divMod n 2
AUTHOR
Helmut Kreindl (euler(AT)chello.at), Jul 31 2009
Square array A(n>=0,k>=0) where A(n,k) gives the (k+1)-th part of the unordered partition which has been encoded in the binary expansion of n, as explained in A227183. The array is scanned antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), etc.
+10
9
0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2
COMMENTS
Discarding the trailing zero terms, on each row n there is a unique partition of integer A227183(n). All possible partitions of finite natural numbers eventually occur. The first partition that sums to n occurs at row A227368(n). Irregular table A227739 lists only the nonzero terms.
EXAMPLE
The top-left corner of the array:
row # row starts as
0 0, 0, 0, 0, 0, ...
1 1, 0, 0, 0, 0, ...
2 1, 1, 0, 0, 0, ...
3 2, 0, 0, 0, 0, ...
4 2, 2, 0, 0, 0, ...
5 1, 1, 1, 0, 0, ...
6 1, 2, 0, 0, 0, ...
7 3, 0, 0, 0, 0, ...
8 3, 3, 0, 0, 0, ...
9 1, 2, 2, 0, 0, ...
10 1, 1, 1, 1, 0, ...
11 2, 2, 2, 0, 0, ...
12 2, 3, 0, 0, 0, ...
13 1, 1, 2, 0, 0, ...
14 1, 3, 0, 0, 0, ...
15 4, 0, 0, 0, 0, ...
16 4, 4, 0, 0, 0, ...
17 1, 3, 3, 0, 0, ...
etc.
8 has binary expansion "1000", whose runlengths are [3,1] (the length of the run in the least significant end comes first) which maps to nonordered partition {3+3} as explained in A227183, thus row 8 begins as 3, 3, 0, 0, ... 17 has binary expansion "10001", whose runlengths are [1,3,1] which maps to nonordered partition {1,3,3}, thus row 17 begins as 1, 3, 3, ...
PROG
(Scheme)
(define (A227189bi n k) (cond ((< ( A005811 n) (+ 1 k)) 0) ((zero? k) ( A136480 n)) (else (+ (- ( A136480 n) 1) (A227189bi ( A163575 n) (- k 1))))))
CROSSREFS
Only nonzero terms: A227739. Row sums: A227183. The product of nonzero terms on row n>0 is A227184(n). Number of nonzero terms on each row: A005811. The leftmost column, after n>0: A136480. The rightmost nonzero term: A227185.
Search completed in 0.022 seconds
|