Paul Zimmermann - cp's OEIS frontend

A338089 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg three steps away.

3, 10, 21, 40, 75, 134, 233, 400, 683, 1166, 1981, 3364, 5711, 9690, 16433, 27872, 47267, 80150, 135909, 230460, 390775

Offset: 1

Paul Zimmermann, Oct 09 2020

			For n=2, assume the two disks are on North initially, first move the smallest one to South in 2 moves, then the largest one to East in 1 move, the smallest one back to North in 2 moves, the largest one to West in 2 moves, and finally the smallest one to West in 3 moves, with a total of 10 moves. Each disk has a number of moves which is 3 mod 4, thus a(n) == 3*n (mod 4).

Martin Ehrenstein, (C++) Program for A338024 (computes terms of this sequence, too)

Cf. A292764, A338024.

Conjecture: a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-5) for n > 9 (the same recurrence as conjectured in A292764 and A338024). - Pontus von Brömssen, Oct 12 2020

a(n) ~ k*r^n, k = (725 + (310451786 - 3203949*sqrt(87))^(1/3) + (310451786 + 3203949*sqrt(87))^(1/3))/348, r=constant of A289265 (closed-form by Amiram Eldar via von Brömssen conjecture). - Bill McEachen, Aug 19 2025

a(17)-a(21) from Martin Ehrenstein, Oct 26 2020

A338024 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg one step away.

Original entry on oeis.org

1, 6, 15, 28, 57, 98, 179, 304, 521, 894, 1519, 2576, 4381, 7434, 12603, 21380, 36265, 61486, 104263, 176808, 299797

Offset: 1

Paul Zimmermann, Oct 07 2020

			For n=2, assume the two disks are on North initially, first move the smallest one to West in 3 moves, then the largest one to East in 1 move, and the smallest one to East also in 2 moves, with a total of 6 moves. Each disk has a number of moves which is 1 mod 4, thus a(n) = n mod 4.

Martin Ehrenstein, (C++) Program

Cf. A292764, A338089.

Conjecture: a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-5) for n > 11.

Conjectured g.f.: x*(1+5*x+8*x^2+6*x^3+8*x^4+8*x^6-4*x^8+4*x^9-4*x^10)/((1-x)*(1+x)*(1-x-2*x^3)). - Stefano Spezia, Oct 07 2020 after Paul Zimmermann

a(17)-a(21) from Martin Ehrenstein, Oct 25 2020

A333553 a(n) = A333552(A333551(n)): indices of terms in Recamán's sequence A005132 where the construction avoided a record-sized collision.

Original entry on oeis.org

3, 6, 7, 18, 19, 34, 67, 102, 115, 173, 190, 288, 453, 511, 677, 846, 986, 1230, 1305, 1349, 1715, 2066, 2422, 2870, 3870, 4139, 4599, 4649, 5027, 5899, 7676, 8220, 8742, 9558, 11542, 13144, 13511, 15541, 16001, 16281, 16685, 17199, 18279, 19463, 21267, 23375, 23976, 24260, 24381, 24398, 24399, 55506, 68108, 75688

Offset: 1

N. J. A. Sloane, May 03 2020, following a suggestion from Paul Zimmermann

nonn

			After we have found A005132(6)=13, we attempt to subtract 7 from 13 to get a(7). However, this would give 6, which is a collision, since we already have A005132(3)=6. Furthermore, 6 is larger than any collision we have so far avoided. So 7 (the index of the term of A005132 that we were constructing), gets added to the current sequence (it is a(3)).

Rémy Sigrist, Table of n, a(n) for n = 1..365
Index entries for sequences related to Recamán's sequence
Rémy Sigrist, C++ program for A333553

Cf. A005132, A333548, A333549, A333550, A333551, A333552.

A333550 Records in A333549.

Original entry on oeis.org

0, 1, 6, 7, 24, 45, 90, 163, 264, 285, 453, 514, 909, 912, 961, 1687, 1707, 1743, 2941, 2947, 3136, 5037, 5313, 5561, 5809, 9586, 9916, 9929, 10118, 10318, 17626, 18026, 18419, 18753, 18783, 18952, 31942, 33709, 34027, 34153, 34377, 34482, 34494

Offset: 1

N. J. A. Sloane, May 03 2020, following a suggestion from Paul Zimmermann

nonn

Needs a larger b-file.

Chai Wah Wu, Table of n, a(n) for n = 1..423 (n = 1..62 from N. J. A. Sloane)
Index entries for sequences related to Recamán's sequence

Cf. A005132, A333549, A333551.

A301810 Smallest prime that starts a sequence of at least n consecutive primes with a difference of 210.

Original entry on oeis.org

2, 20831323, 264860525297, 110176968196069, 21128733495648197, 2537788218640453109

Offset: 1

Paul Zimmermann, Mar 27 2018

a(n) is the first prime of the sequence.
a(1) = 2. Thereafter, a(n) = smallest p such that p + 210*(k-1) and p + 210*k are consecutive primes for all 1 <= k <= n - 1. - Altug Alkan, Mar 27 2018
a(7) <= 71137654873189893604531. - Paul Zimmermann, Nov 12 2018

			a(2)=20831323 since the first prime gap of 210 starts at 20831323.

Cf. A002386, A116495.

a(6) from Paul Zimmermann, Nov 12 2018

A292764 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg two steps away.

Original entry on oeis.org

2, 8, 18, 36, 66, 120, 210, 360, 618, 1052, 1790, 3040, 5162, 8756, 14854, 25192, 42722, 72444, 122846, 208304, 353210

Offset: 1

N. J. A. Sloane, Sep 27 2017, following a suggestion from Paul Zimmermann who computed the terms through a(16)

Paul K. Stockmeyer, Variations on the Four-Post Tower of Hanoi Puzzle, Congressus Numerantium 102 (1994), pp. 3-12;
Paul Zimmermann, Sage program
Index entries for sequences related to Towers of Hanoi

Cf. A292765.

Conjecture: for n >= 9, a(n) = a(n-1)+2*a(n-3)+c(n), where c(n) = 18 for odd n and c(n) = 14 for even n. - Paul Zimmermann, Oct 23 2017
Conjectures from Colin Barker, Oct 25 2017: (Start)
G.f.: 2*x*(1 + 3*x + 4*x^2 + 4*x^3 + 2*x^4 + 2*x^5 + 2*x^6 - 2*x^9) / ((1 - x)*(1 + x)*(1 - x - 2*x^3)).
a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-5) for n>10. [corrected by Paul Zimmermann, Oct 07 2020]
(End)

Extended through a(21) by Paul Zimmermann, Oct 23 2017

Name clarified by Paul Zimmermann, Oct 29 2017

A182216 Number of permutations sortable by a double-ended queue.

Original entry on oeis.org

1, 1, 2, 6, 24, 116, 634, 3762, 23638, 154816, 1046010, 7239440, 51069582, 365879686, 2654987356, 19473381290, 144138193538, 1075285161294, 8076634643892, 61028985689976, 463596673890280, 3538275218777642

Offset: 0

Paul Zimmermann, Apr 19 2012

nonn

			Up to n=4 all permutations can be sorted by a double-ended queue (deque for short).
For n=5 the permutation 24351 cannot: you first queue 2 on either side, then 4 on either side, then 3 has to be queued on the same side as 4 otherwise it will "block" 2 between 3 and 4, but then whatever side you queue 5, you will block either 2 (between 4 and 5) or 3 (between 4 and 5).

Daniel Denton and Peter Doyle, Table of n, a(n) for n = 0..100
Michael Albert, Mike Atkinson, Steve Linton, Permutations generated by stacks and deques, Annals of Combinatorics, 14 (2010) 3-16. (gives method of computation).
Daniel Denton, Methods of computing deque sortable permutations given complete and incomplete information, arXiv:1208.1532.
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
Andrew Elvey-Price and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, arxiv:1508.02273, 2015
Philippe Flajolet, Bruno Salvy and Paul Zimmermann, Lambda-Upsilon-Omega, The 1989 CookBook, page 105.
Paul Zimmermann, C program for A182216
P. Zimmermann, Introduction to Automatic Analysis, 2012.

Cf. A215257, A216040, A215252.

a(13)-a(14) confirmed by Michael Albert, Apr 19 2012
a(16)-a(21) from Michael Albert, Jun 27 2012
a(0)=1 added by N. J. A. Sloane, Sep 12 2012

A073571 Irreducible trinomials: numbers n such that x^n + x^k + 1 is an irreducible polynomial (mod 2) for some k with 0 < k < n.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 17, 18, 20, 21, 22, 23, 25, 28, 29, 30, 31, 33, 34, 35, 36, 39, 41, 42, 44, 46, 47, 49, 52, 54, 55, 57, 58, 60, 62, 63, 65, 66, 68, 71, 73, 74, 76, 79, 81, 84, 86, 87, 89, 90, 92, 93, 94, 95, 97, 98, 100, 102, 103, 105, 106, 108, 110, 111, 113

Offset: 1

Paul Zimmermann, Sep 05 2002

nonn

This sequence is infinite: Golomb, "Shift Register Sequences," on p. 96 (1st ed., 1966) states that "It is easy to exhibit an infinite class of irreducible trinomials. viz. x^(2*3^a) + x^(3^a) + 1 for all a = 0, 1, 2, ..., but whose roots have only 3^(a+1) as their period." - A. M. Odlyzko, Dec 05 1997.

S. W. Golomb, "Shift register sequence", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.

Joerg Arndt, Table of n, a(n) for n = 1..1500
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.6.
Index entries for sequences related to trinomials over GF(2)

For the numbers of such trinomials for a given n, see A057646.

See A073726 for primitive trinomials and A001153 for primitive Mersenne trinomials (and references). Complement of A057486. For values of k see A057774.

a := proc(n) local k; for k from 1 to n-1 do if Irreduc(x^n+x^k+1) mod 2 then RETURN(n) fi od; NULL end: [seq(a(n), n=1..130)];

irreducibleQ[n_] := (irr = False; k = 1; While[k < n, If[ Factor[ x^n + x^k + 1, Modulus -> 2] == x^n + x^k + 1, irr = True; Break[]]; k++]; irr); Select[ Range[120], irreducibleQ] (* Jean-François Alcover, Jan 07 2013 *)

is(n)=for(s=1,n-1,if(polisirreducible((x^n+x^s+1)*Mod(1,2)), return(1)));0 \\ Charles R Greathouse IV, May 30 2013

A073639 Numbers k such that x^k + x + 1 is a primitive polynomial modulo 2.

Original entry on oeis.org

2, 3, 4, 6, 7, 15, 22, 60, 63, 127, 153, 471, 532, 865, 900, 1366

Offset: 1

Richard P. Brent and Paul Zimmermann, Sep 05 2002

Subsequence of A002475, which gives k for which the polynomial x^k + x + 1 is irreducible modulo 2. Term m of A002475 belongs to this sequence iff A046932(m) = 2^m - 1.
Note that a(16) = 1366 = A002475(23). For k = A002475(24) and A002475(25), polynomial x^k + x + 1 is not primitive modulo 2, so a(17) >= A002475(26) = 4495.
The following large terms of A002475 do not belong here: 53484, 62481, 83406, 103468. - Max Alekseyev, Aug 18 2015

Joerg Arndt, Matters Computational (The Fxtbook), section 40.9.3 "Irreducible trinomials of the form 1 + x^k + x^d", p.850
I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, LNCS 793, Springer-Verlag, Berlin, 1994, 1-23, See Table 2.
R. P. Brent, Searching for primitive trinomials (mod 2)
R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 1443-1452.
N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 67-69.
N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502-505.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541-554.
N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566-569.
Index entries for sequences related to trinomials over GF(2)

Cf. A002475, A073571, A057486.

Select[Range[2, 1000], PrimitivePolynomialQ[x^# + x + 1, 2] &] (* Robert Price, Sep 19 2018 *)

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

Original entry on oeis.org

1, 3, 7, 9, 17, 21, 25, 27, 43, 51, 59, 63, 71, 75, 79, 81, 113, 129, 145, 153, 169, 177, 185, 189, 205, 213, 221, 225, 233, 237, 241, 243, 307, 339, 371, 387, 419, 435, 451, 459, 491, 507, 523, 531, 547, 555, 563, 567, 599, 615, 631, 639, 655, 663, 671, 675

Offset: 1

Guillaume Hanrot and Paul Zimmermann, Sep 21 2001

Number of ring multiplications needed to multiply two degree-n polynomials using Karatsuba's algorithm.
Number of gates in the AND/OR problem (see Chang/Tsai reference).
a(n) is also the number of odd elements in the n X n symmetric Pascal matrix. - Stefano Spezia, Nov 14 2022

A. A. Karatsuba and Y. P. Ofman, Multiplication of multiplace numbers by automata. Dokl. Akad. Nauk SSSR 145, 2, 293-294 (1962).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp. 149-179.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27-28.

Cf. A023416, A267584, A047999 (Sierpinski triangle).
Cf. also A268514.
Sequences of form a(n)=r*a(ceil(n/2))+s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.

[n le 1 select 1 else Self(Floor(n/2)) + 2*Self(Ceiling(n/2)): n in [1..60]]; // Vincenzo Librandi, Aug 30 2016

f:=proc(n) option remember; if n=1 then 1 elif n mod 2 = 0 then 3*f(n/2) else 2*f((n+1)/2)+f((n-1)/2); fi; end; [seq(f(n),n=1..60)]; # N. J. A. Sloane, Jan 17 2016

a[n_] := a[n] = If[EvenQ[n], 3 a[n/2], 2 a[# + 1] + a[#] &[(n - 1)/2]]; a[1] = 1; Array[a, 56] (* Michael De Vlieger, Oct 29 2022 *)

a(n) = sum(i=0, n-1, sum(j=0, n-1, binomial(i+j, i) % 2)); \\ Michel Marcus, Aug 25 2013

Partial sums of the sequence { b(1)=1, b(n)=2^(e0(n-1)+1) } (essentially A267584), where e0(n)=A023416(n) is the number of zeros in the binary expansion of n. [Chang/Tsai] - Ralf Stephan, Jul 29 2003
a(1) = 1, a(n) = a(floor(n/2)) + 2*a(ceiling(n/2)), n > 1.
a(n+1) = Sum_{0<=i, j<=n} (binomial(i+j, i) mod 2). - Benoit Cloitre, Mar 07 2005
In particular, a(2^k)=3^k, a(3*2^k)=7*3^k. - N. J. A. Sloane, Jan 18 2016
a(n) = 2*A268514(n-1) + 1. - N. J. A. Sloane, Feb 07 2016

Edited with clearer definition by N. J. A. Sloane, Jan 18 2016

cp's OEIS Frontend

User: Paul Zimmermann

A338089 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg three steps away.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A338024 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg one step away.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A333553 a(n) = A333552(A333551(n)): indices of terms in Recamán's sequence A005132 where the construction avoided a record-sized collision.

Views

Author

Keywords

Examples

Links

Crossrefs

A333550 Records in A333549.

Views

Author

Keywords

Comments

Links

Crossrefs

A301810 Smallest prime that starts a sequence of at least n consecutive primes with a difference of 210.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A292764 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg two steps away.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A182216 Number of permutations sortable by a double-ended queue.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A073571 Irreducible trinomials: numbers n such that x^n + x^k + 1 is an irreducible polynomial (mod 2) for some k with 0 < k < n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A073639 Numbers k such that x^k + x + 1 is a primitive polynomial modulo 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

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