A085296 -id:A085296 - cp's OEIS frontend

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.

1, 3, 2, 10, 3, 7, 4, 36, 5, 11, 6, 26, 7, 15, 8, 136, 9, 19, 10, 42, 11, 23, 12, 100, 13, 27, 14, 58, 15, 31, 16, 528, 17, 35, 18, 74, 19, 39, 20, 164, 21, 43, 22, 90, 23, 47, 24, 392, 25, 51, 26, 106, 27, 55, 28, 228, 29, 59, 30, 122, 31, 63, 32, 2080, 33, 67, 34, 138, 35

Offset: 1

Johannes W. Meijer, Dec 24 2012

The a(n) appeared in the analysis of A220002, a sequence related to the Catalan numbers.
The first Maple program makes use of a program by Peter Luschny for the calculation of the a(n) values. The second Maple program shows that this sequence has a beautiful internal structure, see the first formula, while the third Maple program makes optimal use of this internal structure for the fast calculation of a(n) values for large n.
The cross references lead to sequences that have the same internal structure as this sequence.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences with simple ordinary generating functions, The OEIS, Jan 01 2004.

Cf. A000027 (the natural numbers), A000120 (1's-counting sequence), A000265 (remove 2's from n), A001316 (Gould's sequence), A001511 (the ruler function), A003484 (Hurwitz-Radon numbers), A003602 (a fractal sequence), A006519 (highest power of 2 dividing n), A007814 (binary carry sequence), A010060 (Thue-Morse sequence), A014577 (dragon curve), A014707 (dragon curve), A025480 (nim-values), A026741, A035263 (first Feigenbaum symbolic sequence), A037227, A038712, A048460, A048896, A051176, A053381 (smooth nowhere-zero vector fields), A055975 (Gray code related), A059134, A060789, A060819, A065916, A082392, A085296, A086799, A088837, A089265, A090739, A091512, A091519, A096268, A100892, A103391, A105321 (a fractal sequence), A109168 (a continued fraction), A117973, A129760, A151930, A153733, A160467, A162728, A181988, A182241, A191488 (a companion to Gould's sequence), A193365, A220466 (this sequence).

-- Following Ralf Stephan's recurrence:
import Data.List (transpose)
a220466 n = a006519_list !! (n-1)
a220466_list = 1 : concat
   (transpose [zipWith (-) (map (* 4) a220466_list) a006519_list, [2..]])
-- Reinhard Zumkeller, Aug 31 2014

# First Maple program
a := n -> 2^padic[ordp](n, 2)*(n+1)/2 : seq(a(n), n=1..69); # Peter Luschny, Dec 24 2012
# Second Maple program
nmax:=69: 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) := 4^p*(n-1)  + 2^(p-1)*(1+2^p) od: od: seq(a(n), n=1..nmax);
# Third Maple program
nmax:=69: for p from 0 to ceil(simplify(log[2](nmax))) do n:=2^p: n1:=1: while n <= nmax do a(n) := 4^p*(n1-1)+2^(p-1)*(1+2^p): n:=n+2^(p+1): n1:= n1+1: od: od:  seq(a(n), n=1..nmax);

A220466 = Module[{n, p}, p = IntegerExponent[#, 2]; n = (#/2^p + 1)/2; 4^p*(n - 1) + 2^(p - 1)*(1 + 2^p)] &; Array[A220466, 50] (* JungHwan Min, Aug 22 2016 *)

a(n)=if(n%2,n\2+1,4*a(n/2)-2^valuation(n/2,2)) \\ Ralf Stephan, Dec 17 2013

a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1. Observe that a(2^p) = A007582(p).
a(n) = ((n+1)/2)*(A060818(n)/A060818(n-1))
a(n) = (-1/64)*(q(n+1)/q(n))/(2*n+1) with q(n) = (-1)^(n+1)*2^(4*n-5)*(2*n)!*A060818(n-1) or q(n) = (1/8)*A220002(n-1)*1/(A098597(2*n-1)/A046161(2*n))*1/(A008991(n-1)/A008992(n-1))
Recurrence: a(2n) = 4a(n) - 2^A007814(n), a(2n+1) = n+1. - Ralf Stephan, Dec 17 2013

A265100 a(n) = 9*A005836(n) + 5, n >= 1.

Original entry on oeis.org

5, 14, 32, 41, 86, 95, 113, 122, 248, 257, 275, 284, 329, 338, 356, 365, 734, 743, 761, 770, 815, 824, 842, 851, 977, 986, 1004, 1013, 1058, 1067, 1085, 1094, 2192, 2201, 2219, 2228, 2273, 2282, 2300, 2309, 2435, 2444, 2462, 2471, 2516, 2525

Offset: 1

L. Edson Jeffery, Dec 01 2015

nonn

Let C(m) denote the m-th Catalan number (A000108). Let == denote congruence and =!= its negation. Vladimir Reshetnikov asked (see link) how many n exist such that C(n) == 1 (mod 6). It was pointed out by Robert Israel that the only known n are in {1,3,31,255}. Since C(n) is odd if and only if n = 2^m - 1, for some m, Emmanuel Vantieghem (see links) stated the stronger conjecture that C(2^n-1) == 0 (mod 3), for all n>8. This is the motivation for the following.
If n is an integer such that the congruences C(n) == 0 (mod 3) and C(n-1) =!= 0 (mod 3) hold simultaneously, then we call n a "block number." A sequence {n, n+1, ..., n+k-1} of consecutive numbers is called a "block" (of order k), if C(n+i) == 0 (mod 3), for all i such that 0 <= i < k, and if C(n-1) =!= 0 (mod 3) (i.e., if n is a block number) and C(n+k) =!= 0 (mod 3).
If m is an integer such that the congruences C(m) =!= 0 (mod 3) and C(m-1) == 0 (mod 3) hold simultaneously, then we call m a "gap number." A sequence {m, m+1, ..., m+j-1} of consecutive numbers is called a "gap" (of order j), if C(m+i) =!= 0 (mod 3), for all i such that 0 <= i < j, and if C(m-1) == 0 (mod 3) (i.e., if m is a gap number) and C(m+j) == 0 (mod 3). (The sequence A265104 is conjectured to contain all possible gap numbers.) If C(n) == 0 (mod 3), then we say that n is "gap-avoiding."
It follows that if {n, n+1, ..., n+k-1} is a block with block number n, then n+k is a gap number, and if {m, m+1, ..., m+j-1} is a gap with gap number m, then m+j is a block number.
Conjecture 1: The sequence contains all possible block numbers.
Conjecture 2: If m is a block number, then 3*m - 1 is a block number.
Conjecture 3: If C(n) == 0 (mod 3), then C(3*n-1) == 0 (mod 3) or, what is the same thing, if n lies in a block, then 3*n - 1 lies in a block.
Conjecture 4: Assuming that A265104 contains all possible gap numbers, let B(n) denote the block with block number a(n), n >= 1, so that B(n) = {a(n), a(n)+1, ..., A265104(n)-1}. The (flattened) sequence {B(1), B(2), ...} of blocks contains all numbers m such that the base 3 representations of m and m+1 both contain at least one 2 and is identical to A111018.
Conjecture 5: C(n) == 0 (mod 3) if and only if the base 3 representations of n and n + 1 both contain at least one 2. [This conjecture has been proved by Robert Israel (see link for the proof)].
Theorem 1: The following statements are equivalent to Vantieghem's conjecture stated above: (i) For all m>8, 2^m-1 is gap-avoiding; (ii) C(2^n-1) == 0 (mod 3) if and only if the base 3 representations of 2^n - 1 and 2^n both contain at least one 2.
Proof: For (i), the statement obviously follows from the definitions, and (ii) follows from the proof of Conjecture 5.

Robert Israel, A000108(n) == 1 (mod 6), Sequence Fans Mailing List, December 2015.
Vladimir Reshetnikov, A000108(n) == 1 (mod 6), Sequence Fans Mailing List, November 2015.
Emmanuel Vantieghem, A000108(n) == 1 (mod 6), Sequence Fans Mailing List, November 2015.
Emmanuel Vantieghem, A000108(n) == 1 (mod 6), Sequence Fans Mailing List, November 2015.

A000108 (Catalan numbers).

Cf. A085296, A111018, A265104.

a005836[1] := 0; a005836[n_] := If[OddQ[n], 3*a005836[Floor[(n + 1)/2]], a005836[n - 1] + 1]; a265100[n_] := 9*a005836[n] + 5; Table[a265100[n], {n, 46}]
5 + 9 Join[{0}, Accumulate[Table[(3^IntegerExponent[n, 2] + 1)/2, {n, 57}]]] (* Vincenzo Librandi, Dec 03 2015 *)

Conjecture: a(n) = A265104(n) - A085296(n).

A265104 a(n) = A265100(n+1) - 6, n >= 1.

Original entry on oeis.org

8, 26, 35, 80, 89, 107, 116, 242, 251, 269, 278, 323, 332, 350, 359, 728, 737, 755, 764, 809, 818, 836, 845, 971, 980, 998, 1007, 1052, 1061, 1079, 1088, 2186, 2195, 2213, 2222, 2267, 2276, 2294, 2303, 2429, 2438, 2456, 2465, 2510, 2519, 2537

Offset: 1

L. Edson Jeffery, Dec 01 2015

nonn

In the following, let "gap" and "gap number" be as defined in A265100, and let C(m) denote the m-th Catalan number (A000108).
Conjecture 1: The sequence contains all possible gap numbers.
Conjecture 2: For any gap G, the order |G| of G is the constant |G| = 6.
Conjecture 3: If g is a gap number, then 3*g + 2 is a gap number.
Conjecture 4: If C(m) =!= 0 (mod 3), then C(3*m+1) =!= 0 (mod 3) (=!= means "not congruent") or, what is the same thing, if m lies in a gap, then 3*m + 1 lies in a gap.

Cf. A265100.

a005836[1] := 0; a005836[n_] := If[OddQ[n], 3*a005836[Floor[(n + 1)/2]], a005836[n - 1] + 1]; a265100[n_] := 9*a005836[n] + 5; a265104[n_] := a265100[n+1] - 6; Table[a265104[n], {n, 46}]
(* Or: *)
a007814[x_] := IntegerExponent[x, 2]; a003602[x_] := (1 + x/2^a007814[x])/2; a005836[1] := 0; a005836[n_] := If[OddQ[n], 3*a005836[Floor[(n + 1)/2]], a005836[n - 1] + 1]; a265100[n_] := 9*a005836[n] + 5; a265104[n_] := (3^(a007814[n] + 2) - 3)/2 + a265100[2^(a007814[n])*(2*a003602[n] - 1)]; Table[a265104[n], {n, 46}]

a(n) = (3^(A007814(n) + 2) - 3)/2 + A265100(2^(A007814(n))*(2*A003602(n) - 1)), n >= 1.

Conjecture: a(n) = A265100(n) + A085296(n).

A111018 Indices of Catalan numbers that are divisible by 3.

Original entry on oeis.org

5, 6, 7, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 32, 33, 34, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 86, 87, 88, 95, 96, 97, 98, 99, 100

Offset: 1

Robert G. Wilson v, Sep 09 2005

nonn

Conjecture: The sequence contains all numbers n such that n and n+1 are both in the sequence A074940, or, equivalently, such that neither n nor n+1 is in the sequence A005836. - L. Edson Jeffery, Dec 02 2015

The asymptotic density of this sequence is 1 (Burns, 2016). - Amiram Eldar, Jan 26 2021

G. C. Greubel, Table of n, a(n) for n = 1..1000
Rob Burns, Asymptotic density of Catalan numbers modulo 3 and powers of 2, arXiv:1611.03705 [math.NT], 2016.

Cf. A000108.

Cf. A085296, A265100, A265104.

[n: n in [1..200] | Binomial(2*n, n) div (n+1) mod 3 eq 0]; // Vincenzo Librandi, Dec 03 2015

Flatten[Position[CatalanNumber[Range[100]],?(Divisible[#,3]&)]] (* _Harvey P. Dale, Oct 25 2011 *)
Select[Range@100, Divisible[CatalanNumber@#,3]&] (* Vladimir Reshetnikov, Nov 06 2015 *)

for(n=0, 1e3, if(binomial(2*n, n)/(n+1) % 3 == 0, print1(n, ", "))) \\ Altug Alkan, Dec 02 2015

A085297 Nonzero residues of Catalan sequence modulo 3; related to the Thue-Morse sequence (A001285).

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2

Offset: 1

Paul D. Hanna, Jun 24 2003

nonn

The runs of zeros in between the digit strings are given in A085296.

Cf. A001285 (Thue-Morse), A000108 (Catalan), A039969 (d-perfect), A085296.

If a leading '1' is added to the Catalan sequence modulo 3, the only nonzero digit strings are {1, 1, 1, 2, 2, 2} and {2, 2, 2, 1, 1, 1}. Replacing these digit strings with their first digit, {1, 1, 1, 2, 2, 2} -> '1' and {2, 2, 2, 1, 1, 1} -> '2', then omitting all zeros, results in the Thue-Morse sequence.

cp's OEIS Frontend

A220466 a((2*n-1)*2^p) = 4^p*(n-1) + 2^(p-1)*(1+2^p), p >= 0 and n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A265100 a(n) = 9*A005836(n) + 5, n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A265104 a(n) = A265100(n+1) - 6, n >= 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A111018 Indices of Catalan numbers that are divisible by 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A085297 Nonzero residues of Catalan sequence modulo 3; related to the Thue-Morse sequence (A001285).

Views

Author

Keywords

Comments

Crossrefs

Formula

A220466 a((2n-1)2^p) = 4^p(n-1) + 2^(p-1)(1+2^p), p >= 0 and n >= 1.