A046699 -id:A046699 - cp's OEIS frontend

A055938 Integers not generated by b(n) = b(floor(n/2)) + n (complement of A005187).

2, 5, 6, 9, 12, 13, 14, 17, 20, 21, 24, 27, 28, 29, 30, 33, 36, 37, 40, 43, 44, 45, 48, 51, 52, 55, 58, 59, 60, 61, 62, 65, 68, 69, 72, 75, 76, 77, 80, 83, 84, 87, 90, 91, 92, 93, 96, 99, 100, 103, 106, 107, 108, 111, 114, 115, 118, 121, 122, 123, 124, 125, 126, 129

Offset: 1

Alford Arnold, Jul 21 2000

Note that the lengths of the consecutive runs in a(n) form sequence A001511.
Integers that are not a sum of distinct integers of the form 2^k-1. - Vladeta Jovovic, Jan 24 2003
Also n! never ends in this many 0's in base 2 - Carl R. White, Jan 21 2008
A079559(a(n)) = 0. - Reinhard Zumkeller, Mar 18 2009
These numbers are dead-end points when trying to apply the iterated process depicted in A071542 in reverse, i.e. these are positive integers i such that there does not exist k with A000120(i+k)=k. See also comments at A179016. - Antti Karttunen, Oct 26 2012
Conjecture: a(n)=b(n) defined as b(1)=2, for n>1, b(n+1)=b(n)+1 if n is already in the sequence, b(n+1)=b(n)+3 otherwise. If so, then see Cloitre comment in A080578. - Ralf Stephan, Dec 27 2013
Numbers n for which A257265(m) = 0. - Reinhard Zumkeller, May 06 2015. Typo corrected by Antti Karttunen, Aug 08 2015
Numbers which have a 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 28 2025

			Since A005187 begins 0 1 3 4 7 8 10 11 15 16 18 19 22 23 25 26 31... this sequence begins 2 5 6 9 12 13 14 17 20 21

Complement of A005187. Setwise difference of A213713 and A213717.
Row 1 of arrays A257264, A256997 and also of A255557 (when prepended with 1). Equally: column 1 of A256995 and A255555.
Cf. also arrays A254105, A254107 and permutations A233276, A233278.
Left inverses: A234017, A256992.
Cf. A001511, A046699, A079559, A080578, A086343, A227359, A227408, A234016.
Gives positions of zeros in A213714, A213723, A213724, A213731, A257265, positions of ones in A213725-A213727 and A256989, positions of nonzeros in A254110.
Cf. also A010061 (integers that are not a sum of distinct integers of the form 2^k+1).
Analogous sequence for factorial base number system: A219658, for Fibonacci number system: A219638, for base-3: A096346. Cf. also A136767-A136774.
Cf. A257508, A257509, A257126.

a055938 n = a055938_list !! (n-1)
a055938_list = concat $
   zipWith (\u v -> [u+1..v-1]) a005187_list $ tail a005187_list
-- Reinhard Zumkeller, Nov 07 2011

a[0] = 0; a[1] = 1; a[n_Integer] := a[Floor[n/2]] + n; b = {}; Do[ b = Append[b, a[n]], {n, 0, 105}]; c =Table[n, {n, 0, 200}]; Complement[c, b]
(* Second program: *)
t = Table[IntegerExponent[(2n)!, 2], {n, 0, 100}]; Complement[Range[t // Last], t] (* Jean-François Alcover, Nov 15 2016 *)

L=listcreate();for(n=1,1000,for(k=2*n-hammingweight(n)+1,2*n+1-hammingweight(n+1),listput(L,k)));Vec(L) \\ Ralf Stephan, Dec 27 2013

def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a043545(n):
    x=bin(n)[2:]
    return int(max(x)) - int(min(x))
def a079559(n): return 1 if n==0 else a043545(n + 1)*a079559(n + 1 - a053644(n + 1))
print([n for n in range(1, 201) if a079559(n)==0]) # Indranil Ghosh, Jun 11 2017, after the comment by Reinhard Zumkeller

;; utilizing COMPLEMENT-macro from Antti Karttunen's IntSeq-library)
(define A055938 (COMPLEMENT 1 A005187))
;; Antti Karttunen, Aug 08 2015

a(n) = A080578(n+1) - 2 = A080468(n+1) + 2*n (conjectured). - Ralf Stephan, Dec 27 2013
From Antti Karttunen, Aug 08 2015: (Start)
Other identities. For all n >= 1:
A234017(a(n)) = n.
A256992(a(n)) = n.
A257126(n) = a(n) - A005187(n).
(End)

More terms from Robert G. Wilson v, Jul 24 2000

A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1

Offset: 0

Vladeta Jovovic, Jan 25 2003

Differences of the Meta-Fibonacci sequence for s=0. - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
Fixed point of morphism 0-->0, 1-->110 - Joerg Arndt, Jun 07 2007
A006697(k) gives number of distinct subwords of length k, conjectured to be equal to A094913(k)+1. - M. F. Hasler, Dec 19 2007
Characteristic function for the range of A005187: a(A055938(n))=0; a(A005187(n))=1; if a(m)=1 then either a(m-1)=1 or a(m+1)=1. - Reinhard Zumkeller, Mar 18 2009
The number of zeros between successive pairs of ones in this sequence is A007814. - Franklin T. Adams-Watters, Oct 05 2011
Length of n-th run = abs(A088705) + 1. - Reinhard Zumkeller, Dec 11 2011

			a(11)=1 because we have [7,3,1].
G.f. = 1 + x + x^3 + x^4 + x^7 + x^8 + x^10 + x^11 + x^15 + x^16 + x^18 + ...
From _Omar E. Pol_, Nov 30 2009: (Start)
The sequence, displayed as irregular triangle, in which rows length are powers of 2, begins:
1;
1,0;
1,1,0,0;
1,1,0,1,1,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0;
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Gary W. Adamson, Comments on A079559
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26.5, Recursive generation and relation to a power series, page 74, figure 1.26-E and function A.
Benoit Cloitre, Fractal walk generated by the 130000 first terms (step of unit length moving to right if 0 left if 1) starting at (0,0)
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.[alt source]
Thomas M. Lewis and Fabian Salinas, Optimal pebbling of complete binary trees and a meta-Fibonacci sequence, arXiv:2109.07328 [math.CO], 2021.
F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3. [This is a later version than that in the GenMetaFib.html link]
Index entries for characteristic functions

Cf. A000929, A001511, A005187, A006697, A007814, A046699, A055938, A094913, A163988.

Cf. A035263, A066519.

a079559 = p $ tail a000225_list where
   p _      0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Dec 11 2011

a079559_list = 1 : f [1] where
   f xs = ys ++ f ys where ys = init xs ++ [1] ++ tail xs ++ [0]
-- Reinhard Zumkeller, May 05 2015

g:=product(1+x^(2^n-1),n=1..15): gser:=series(g,x=0,110): seq(coeff(gser,x,n),n=0..104); # Emeric Deutsch, Apr 06 2006
d := n -> if n=1 then 1 else A046699(n)-A046699(n-1) fi; # Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

row[1] = {1}; row[2] = {1, 0}; row[n_] := row[n] = row[n-1] /. 1 -> Sequence[1, 1, 0]; Table[row[n], {n, 1, 7}] // Flatten (* Jean-François Alcover, Jul 30 2012, after Omar E. Pol *)
CoefficientList[ Series[ Product[1 + x^(2^n - 1), {n, 6}], {x, 0, 104}], x] (* or *)
Nest[ Flatten[# /. {0 -> {0}, 1 -> {1, 1, 0}}] &, {1}, 6] (* Robert G. Wilson v, Sep 08 2014 *)

w="1,";for(i=1,5,print1(w=concat([w,w,"0,"])))

A079559(n,w=[1])=until(n<#w=concat([w,w,[0]]),);w[n+1] \\ M. F. Hasler, Dec 19 2007

{a(n) = if( n<0, 0, polcoeff( prod(k=1, #binary(n+1), 1 + x^(2^k-1), 1 + x * O(x^n)), n))} /* Michael Somos, Aug 03 2009 */

def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a043545(n):
    x=bin(n)[2:]
    return int(max(x)) - int(min(x))
l=[1]
for n in range(1, 101): l+=[a043545(n + 1)*l[n + 1 - a053644(n + 1)], ]
print(l) # Indranil Ghosh, Jun 11 2017

G.f.: Product_{n>=1} (1 + x^(2^n-1)).
a(n) = 1 if n=0, otherwise A043545(n+1)*a(n+1-A053644(n+1)). - Reinhard Zumkeller, Aug 19 2006
a(n) = p(n,1) with p(n,k) = p(n-k,2*k+1) + p(n,2*k+1) if k <= n, otherwise 0^n. - Reinhard Zumkeller, Mar 18 2009
Euler transform is sequence A111113 sequence offset -1. - Michael Somos, Aug 03 2009
G.f.: Product_{k>0} (1 - x^k)^-A111113(k+1). - Michael Somos, Aug 03 2009
a(n) = A108918(n+1) mod 2. - Joerg Arndt, Apr 06 2011
a(n) = A000035(A153000(n)), n >= 1. - Omar E. Pol, Nov 29 2009, Aug 06 2013

Edited by M. F. Hasler, Jan 03 2008

A213714 Inverse function for injection A005187.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 26 2012

nonn

a(0)=0; thereafter if n occurs as a term of A005187, a(n)=its position in A005187, otherwise zero. This works as an "inverse" function for A005187 in a sense that a(A005187(n)) = n for all n.

a(n)*A234017(n) = 0 for all n.

Antti Karttunen, Table of n, a(n) for n = 0..8192

Can be used when computing A213715, A213723, A213724, A233275, A233277. Cf. A005187, A046699, A079559, A234017, A230414.

import Data.List (genericIndex)
a213714 n = genericIndex a213714_list n
a213714_list = f [0..] a005187_list 0 where
   f (x:xs) ys'@(y:ys) i | x == y    = i : f xs ys (i+1)
                         | otherwise = 0 : f xs ys' i
-- Reinhard Zumkeller, May 01 2015

from sympy import factorial
def a046699(n):
    if n<3: return 1
    s=1
    while factorial(2*s)%(2**(n - 1))>0: s+=1
    return s
def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a043545(n):
    x=bin(n)[2:]
    return int(max(x)) - int(min(x))
def a079559(n): return 1 if n==0 else a043545(n + 1)*a079559(n + 1 - a053644(n + 1))
def a(n): return 0 if n==0 else a079559(n)*(a046699(n + 2) - 1) # Indranil Ghosh, Jun 11 2017

a(0)=0, for n>0, a(n) = A079559(n) * (A046699(n+2)-1) [With A046699's October 2012 starting offset. Incorrect indexing shown in this formula corrected by Antti Karttunen, Dec 18 2013]

A007843 Least positive integer k for which 2^n divides k!.

Original entry on oeis.org

1, 2, 4, 4, 6, 8, 8, 8, 10, 12, 12, 14, 16, 16, 16, 16, 18, 20, 20, 22, 24, 24, 24, 26, 28, 28, 30, 32, 32, 32, 32, 32, 34, 36, 36, 38, 40, 40, 40, 42, 44, 44, 46, 48, 48, 48, 48, 50, 52, 52, 54, 56, 56, 56, 58, 60, 60, 62, 64, 64, 64, 64, 64, 64, 66, 68, 68, 70, 72, 72, 72, 74, 76, 76, 78

Offset: 0

Bruce Dearden and Jerry Metzger; R. Muller

Obtained by writing every natural number n k times where 2^k divides n but 2^(k+1) does not divide n. - Amarnath Murthy, Aug 22 2002
An interval of the form (A007814(k!)-A007814(k), A007814(k!)] contains n >= 1 iff k = a(n). - Vladimir Shevelev, Mar 19 2012
It appears than for n > 0, a(n) is divisible by 2, and that the resulting sequence a(n)/2 is A046699 (ignoring first term, this is the Meta-Fibonacci sequence for s=0). - Michel Marcus, Aug 19 2013
The last part is proved in the Kullmann & Zhao preprint, Thm. 3.16. The first statement is obvious: to get a larger power of two in k!, k > 1 must be increased by 2, else the factor is odd and doesn't increase the 2-valuation of k!. The other part also follows from the comment in A046699: "n occurs A001511(n) times", where A001511 = A007814 + 1, A007814 = the number of powers of 2 in k. - M. F. Hasler, Dec 27 2019

H. Ibstedt, Smarandache Primitive Numbers, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 216-229.

T. D. Noe, Table of n, a(n) for n = 0..1000
Oliver Kullmann and Xishun Zhao, Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses, arXiv preprint arXiv:1505.02318 [cs.DM], 2015.
Kevin Ryde, PARI/GP Code and Notes
F. Smarandache, Only Problems, Not Solutions!.
Wikipedia, Legendre's Formula.

Cf. A007814, A007844, A007845, A020646, A048841-A048846.

with(numtheory): ans := [ ]: p := ithprime(1): t0 := 1/p: for n from 0 to 50 do t0 := t0*p: t1 := 1: i := 1: while t1 mod t0 <> 0 do i := i+1: t1 := t1*i: od: ans := [ op(ans),i ]: od: ans;
# Alternative:
N:= 1000: # to get a(0) to a(N)
A:= Array(0..N):
A[0]:= 1:
A[1]:= 2:
B[2]:= 1:
for k from 4 by 2 do
  B[k]:= B[k-2] + padic:-ordp(k,2);
  A[B[k-2]+1..min(N,B[k])]:= k;
  if B[k] >= N then break fi;
od:
seq(A[i],i=0..N); # Robert Israel, Dec 07 2015

a[n_] := (k=0; While[Mod[++k!, 2^n] > 0]; k); Table[a[n], {n, 0, 74}] (* Jean-François Alcover, Dec 08 2011 *)
Join[{1},Module[{nn=100,f},f=Table[{x!,x},{x,0,nn}];Table[ SelectFirst[ f,Divisible[#[[1]],2^n]&],{n,80}]][[All,2]]] (* Harvey P. Dale, Nov 20 2021 *)

a(n)=if(n<0,0,s=1; while(s!%(2^n)>0,s++); s)

a(n) = {k = 1; while (valuation(k!, 2) < n, k++); k;} \\ Michel Marcus, Aug 19 2013

apply( A007843(n)={for(k=1,oo,(n-=valuation(k,2))>0||return(k))}, [0..99]) \\ This idea can also be used to compute most efficiently a vector a(0..N). - M. F. Hasler, Dec 27 2019

from itertools import count
def A007843(n):
    c = 0
    for k in count(1):
        c += (~k&k-1).bit_length()
        if c >= n:
            return k # Chai Wah Wu, Jul 08 2022

a(n) = A002034(2^n). For n>1, it appears that a(n+1) = a(n)+2 if n is in A005187. - Benoit Cloitre, Sep 01 2002
G.f.: 1 + 2*(x/(1-x))*Product_{k >= 1} (1+x^(2^k-1)). - Wadim Zudilin, Dec 07 2015
a(n) = 2*A046699(n) for n > 0. - Michel Marcus and M. F. Hasler, Dec 27 2019
a(2^i + r) = 2^i + a(r+1) for 0 <= r <= 2^i-2, and a(2^i + r) = 2^(i+1) for r = 2^i-1. - Kevin Ryde, Aug 06 2022

A080578 a(1)=1; for n > 1, a(n) = a(n-1) + 1 if n is already in the sequence, a(n) = a(n-1) + 3 otherwise.

Original entry on oeis.org

1, 4, 7, 8, 11, 14, 15, 16, 19, 22, 23, 26, 29, 30, 31, 32, 35, 38, 39, 42, 45, 46, 47, 50, 53, 54, 57, 60, 61, 62, 63, 64, 67, 70, 71, 74, 77, 78, 79, 82, 85, 86, 89, 92, 93, 94, 95, 98, 101, 102, 105, 108, 109, 110, 113, 116, 117, 120, 123, 124, 125, 126

Offset: 1

N. J. A. Sloane and Benoit Cloitre, Mar 23 2003

nonn

More generally for fixed r, there is a nice connection between the sequence a(1)=1, a(n) = a(n-1) + 1 if n is in the sequence, a(n) = a(n-1) + r + 1 otherwise and the so-called metafibonacci sequences. Indeed, (a(n)-n)/r is a generalized metafibonacci sequence of order r as defined in Ruskey's recent paper (reference given at A046699). - Benoit Cloitre, Feb 04 2007

In the Fokkink-Joshi paper, this sequence is the Cloitre (0,1,1,3)-hiccup sequence. - Michael De Vlieger, Jul 29 2025

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
Robbert Fokkink and Gandhar Joshi, On Cloitre's hiccup sequences, arXiv:2507.16956 [math.CO], 2025. See pp. 3, 5, 11.

Cf. A080455, A080456, A080457, A080458, A080036, A080037, A080468.

a080578 n = a080578_list !! (n-1)
a080578_list = 1 : f 2 [1] where
   f x zs@(z:_) = y : f (x + 1) (y : zs) where
     y = if x `elem` zs then z + 1 else z + 3
-- Reinhard Zumkeller, Sep 26 2014

l={1}; a=1; For[n=2, n<=100, If[MemberQ[l, n], a=a+1, a=a+3]; AppendTo[l, a]; n++]; l (* Indranil Ghosh, Apr 07 2017 *)

a(n)=if(n<2,1,a(n+1-2^floor(log(n)/log(2)))+2*2^floor(log(n)/log(2))-1) \\ Benoit Cloitre, Feb 04 2007

l=[1]
a=1
for n in range(2, 101):
    a += 3 if n not in l else 1
    l.append(a)
print(l) # Indranil Ghosh, Apr 07 2017

a(n) = 2n + O(1); a(2^n) = 2^(n+1). - Benoit Cloitre, Oct 12 2003
a(1) = 1, for n >= 2 a(n) = a(n + 1 - 2^floor(log(n)/log(2))) + 2*2^floor(log(n)/log(2)) - 1; (a(n) - n)/2 = A046699(n) for n >= 2. - Benoit Cloitre, Feb 04 2007
a(n) = A055938(n-1) + 2 (conjectured). - Ralf Stephan, Dec 27 2013

A101925 a(n) = A005187(n) + 1.

Original entry on oeis.org

1, 2, 4, 5, 8, 9, 11, 12, 16, 17, 19, 20, 23, 24, 26, 27, 32, 33, 35, 36, 39, 40, 42, 43, 47, 48, 50, 51, 54, 55, 57, 58, 64, 65, 67, 68, 71, 72, 74, 75, 79, 80, 82, 83, 86, 87, 89, 90, 95, 96, 98, 99, 102, 103, 105, 106, 110, 111, 113, 114, 117, 118, 120, 121, 128, 129

Offset: 0

Ralf Stephan, Dec 28 2004

nonn

Exponent of 2 in the sequences A032184, A052278, A060055, A066318, A088229, A101926.

p(n) sequence for k=2, s=0. p(n) = min(j: A046699(j) = n). - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), #R26, 13 pages.
F. Ruskey, C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3. [This is a later version than that in the GenMetaFib.html link]

Bisection of A089279. First differences are in A001511.
Cf. A000120, A005187, A046699.
Cf. A032184, A052278, A060055, A066318, A088229, A101926.

Table[IntegerExponent[(2 n)!, 2] + 1, {n, 0, 65}] (* or *)
Table[2 n - DigitCount[2 n, 2, 1] + 1, {n, 0, 65}] (* Michael De Vlieger, Feb 04 2017 *)

PARI
```
a(n)=1+sum(k=1, n, valuation(k,2)+1)
```

a(n)=if(n==0,1,if((n%2)==0,2*a(n/2)+subst(Pol(binary(n)),x,1)-1,a(n-1)+1))

a(n)=2*n+1-hammingweight(n) \\ Charles R Greathouse IV, Dec 29 2022
(Python 3.10+)
def A101925(n): return (n<<1)-n.bit_count()+1 # Chai Wah Wu, Jul 13 2022

Recurrence: a(2n) = 2a(n) + A000120(n) - 1, a(2n+1) = a(2n) + 1.

G.f.: (1 / 1-z) * (z + z * sum(z^(2^i) * (s + (1 / (1 - z^(2^k)))),i=0..infinity)). - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

A046702 a(n)=a(n-a(n-1))+a(n-1-a(n-2))+a(n-2-a(n-3)), n>3. a(1)=a(2)=a(3)=1.

Original entry on oeis.org

1, 1, 1, 3, 3, 3, 5, 5, 7, 5, 7, 7, 9, 9, 9, 11, 11, 13, 11, 15, 13, 17, 13, 17, 15, 19, 17, 19, 17, 21, 19, 23, 19, 23, 21, 25, 23, 25, 25, 27, 27, 27, 29, 29, 31, 29, 33, 31, 35, 31, 37, 33, 39, 33, 41, 35, 43, 35, 43, 37, 45, 39, 45, 39, 47, 41, 49, 41, 49, 43, 51, 45, 51, 45

Offset: 1

R. K. Guy

Sequence proposed by Reg Allenby.
Callaghan, Joseph, John J. Chew III, and Stephen M. Tanny. "On the behavior of a family of meta-Fibonacci sequences." SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See T_{0,3} with initial values 1,1,1, as in Fig. 1.6. - N. J. A. Sloane, Apr 16 2014

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
Index entries for Hofstadter-type sequences

Cf. A240833, A240834.

Callaghan et al. (2005)'s sequences T_{0,k}(n) for k=1 through 7 are A000012, A046699, A046702, A240835, A241154, A241155, A240830.

#T_s,k(n) from Callaghan et al. Eq. (1.6). - From N. J. A. Sloane, Apr 16 2014
s:=0; k:=3;
a:=proc(n) option remember; global s,k;
if n <= 2 then 1
elif n = 3 then 1
else
    add(a(n-i-s-a(n-i-1)),i=0..k-1);
fi; end;
t1:=[seq(a(n),n=1..100)];

a[n_] := a[n] = a[n-a[n-1]] + a[n-1-a[n-2]] + a[n-2-a[n-3]]; a[1] = a[2] = a[3] = 1; Array[a, 80] (* Jean-François Alcover, Dec 12 2016 *)

Corrected and extended by Michael Somos

A182105 Number of elements merged by bottom-up merge sort.

Original entry on oeis.org

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

Offset: 1

Dhruv Matani, Apr 12 2012

Also triangle read by rows in which row j lists the first A001511(j) powers of 2, j >= 1, hence records give A000079. Right border gives A006519. Row sums give A038712. The equivalent sequence for partitions is A211009. See example. - Omar E. Pol, Sep 03 2013

It appears that A045412 gives the indices of the terms which are greater than 1. - Carl Joshua Quines, Apr 07 2017

			Using construction (b), the initial values n, u_n, v_n are:
  1, 1, 1
  2, 2, 1
  3, 2, 2
  4, 3, 1
  5, 4, 1
  6, 4, 2
  7, 4, 4
  8, 5, 1
  9, 6, 1
  10, 6, 2
  11, 7, 1
  12, 8, 1
  13, 8, 2
  14, 8, 4
  15, 8, 8
  16, 9, 1
  17, 10, 1
  18, 10, 2
  19, 11, 1
  20, 12, 1
  ...
From _Omar E. Pol_, Sep 03 2013: (Start)
Illustration of initial terms (first 2^5-1 terms):
Written as an irregular triangle: T(j,k) is also the length of the k-th column in the j-th region of the diagram, as shown below. Note that the j-th row of the diagram is equivalent to the j-th composition (in colexicographic order) of 5 (cf. A228525):
------------------------------------
.          Diagram      Triangle
------------------------------------
.  j / k: 1 2 3 4 5  /  1 2 3 4 5
------------------------------------
.         _ _ _ _ _
.  1     |_| | | | |    1;
.  2     |_ _| | | |    1,2;
.  3     |_|   | | |    1;
.  4     |_ _ _| | |    1,2,4;
.  5     |_| |   | |    1;
.  6     |_ _|   | |    1,2;
.  7     |_|     | |    1;
.  8     |_ _ _ _| |    1,2,4,8;
.  9     |_| | |   |    1;
. 10     |_ _| |   |    1,2;
. 11     |_|   |   |    1;
. 12     |_ _ _|   |    1,2,4;
. 13     |_| |     |    1;
. 14     |_ _|     |    1,2;
. 15     |_|       |    1;
. 16     |_ _ _ _ _|    1,2,4,8,16;
...
(End)

Donald E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 6A, Section 7.2.2.2, Eq. (97).
Donald E. Knuth, The Art of Computer Programming, Addison-Wesley (2015) Vol. 4, Fascicle 6, Satisfiability, p. 80, Eq. (130).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Filip Bártek, Karel Chvalovský, and Martin Suda, Regularization in Spider-Style Strategy Discovery and Schedule Construction, arXiv:2403.12869 [cs.AI], 2024. See p. 5.
Michael Luby Alistair, Alistair Sinclair, and David Zuckerman, Optimal speedup of Las Vegas algorithms, Info. Processing Lett., 47 (1993), 173-180.
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, Théophane Weber, Single-Agent Policy Tree Search With Guarantees, arXiv:1811.10928 [cs.AI], 2018, also in Advances in Neural Information Processing Systems, 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.

Cf. A046699, A215020 (a version involving Fibonacci numbers).

A182105_list := proc(n) local L,m,k;
L := NULL;
for m from 1 to n do
for k from 0 to padic[ordp](m, 2) do
L := L,2^k od od;
L; end:
A182105_list(250);
# Peter Luschny, Aug 01 2012, based on Charles R Greathouse IV's PARI program.

Array[Prepend[2^Range@ IntegerExponent[#, 2], 1] &, 48] // Flatten (* Michael De Vlieger, Jan 22 2019 *)

for(n=1,50,for(k=0,valuation(n,2),print1(2^k", "))) \\ Charles R Greathouse IV, Apr 12 2012

The following two constructions are given by Knuth:
(a) a(1) = 1; thereafter a(n+1) = 2a(n) if a(n) has already occurred an even number of times, otherwise a(n+1) = 1.
(b) Set (u_1, v_1) = (1, 1), thereafter (u_{n+1}, v_{n+1}) = ( A ? B : C)
where
A = u_n & -u_n = v_n (where the AND refers to the binary expansions),
B = (u_n + 1, 1) (the result if A is true),
C = (u_n, 2v_n) (the result if A is false).
Then v_n = A182105, u_n = A046699 minus first term.
a(n) = 2^(A082850(n)-1). - Laurent Orseau, Jun 18 2019

Edited by N. J. A. Sloane, Aug 02 2012

A240830 a(n)=1 for n <= s+k; thereafter a(n) = Sum(a(n-i-s-a(n-i-1)),i=0..k-1) where s=0, k=7.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 7, 7, 7, 7, 7, 7, 7, 13, 13, 13, 13, 13, 13, 19, 13, 19, 19, 19, 19, 25, 19, 25, 19, 25, 25, 31, 25, 31, 25, 31, 25, 31, 31, 37, 31, 37, 31, 37, 37, 37, 37, 43, 37, 43, 43, 43, 43, 43, 43, 49, 49, 49, 49, 49, 49, 49, 55, 55, 55, 55, 55, 55, 61, 55, 61, 61, 61, 61, 67, 61, 67, 61, 67, 67, 73

Offset: 1

N. J. A. Sloane, Apr 16 2014

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See Table 2.1.
Index entries for Hofstadter-type sequences

Same recurrence as A240828, A120503 and A046702.
See also A240831, A240832.
Callaghan et al. (2005)'s sequences T_{0,k}(n) for k=1 through 7 are A000012, A046699, A046702, A240835, A241154, A241155, A240830.

#T_s,k(n) from Callaghan et al. Eq. (1.7).
s:=0; k:=7;
a:=proc(n) option remember; global s,k;
if n <= s+k then 1
else
    add(a(n-i-s-a(n-i-1)),i=0..k-1);
fi; end;
t1:=[seq(a(n),n=1..100)];

A240830[n_]:=A240830[n]=If[n<=7,1,Sum[A240830[n-i-A240830[n-i-1]],{i,0,6}]];
Array[A240830,100] (* Paolo Xausa, Dec 06 2023 *)

A226222 a(1) = a(2) = a(3) = 1, a(n) = a(n-2-a(n-2)) + a(n-1-a(n-3)) for n>3.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 9, 10, 10, 11, 11, 11, 12, 13, 13, 13, 14, 15, 16, 16, 16, 17, 18, 18, 18, 18, 19, 20, 21, 21, 21, 21, 22, 22, 23, 23, 24, 25, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 30, 31, 32, 32, 32, 32, 33, 35, 35

Offset: 1

Reinhard Zumkeller, May 31 2013

First numbers not occurring: 62, 66, 75, 79, 114, 123, ... .

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Hofstadter's Q-Sequence
Wikipedia, Hofstadter sequence
Index entries for Hofstadter-type sequences

Cf. A005185, A046699, A063892, A070867.

a226222 n = a226222_list !! (n-1)
a226222_list = 1 : 1 : 1 : zipWith (+)
   (map a226222 $ zipWith (-) [3..] a226222_list)
   (map a226222 $ zipWith (-) [2..] $ tail a226222_list)
-- Reinhard Zumkeller, May 31 2013

a[n_]:= a[n]= If[n<4, 1, a[n-2 -a[n-2]] + a[n-1 -a[n-3]]];
Table[a[n], {n, 80}] (* G. C. Greubel, Mar 28 2022 *)

@CachedFunction
def a(n): # A226222
    if (n<4): return 1
    else: return  a(n-2-a(n-2)) + a(n-1-a(n-3))
[a(n) for n in (1..80)] # G. C. Greubel, Mar 28 2022

a(n) = a(n-2 - a(n-2)) + a(n-1 - a(n-3)), with a(1) = a(2) = a(3) = 1.

cp's OEIS Frontend

A055938 Integers not generated by b(n) = b(floor(n/2)) + n (complement of A005187).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Scheme

Formula

Extensions

A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A213714 Inverse function for injection A005187.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

Formula

A007843 Least positive integer k for which 2^n divides k!.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A080578 a(1)=1; for n > 1, a(n) = a(n-1) + 1 if n is already in the sequence, a(n) = a(n-1) + 3 otherwise.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A101925 a(n) = A005187(n) + 1.

Views

Author

Keywords