Konstantin Knop - cp's OEIS frontend

A384183 a(n) = minimum number of steps required to move n stones from a hole to the next one in an infinite row of holes, where at one step we can move any k stones at once from a hole to the hole at distance k to the left or to the right, and there are n stones overall.

0, 1, 2, 3, 4, 5, 5, 6, 7, 7, 6, 7, 7, 8, 7, 7, 8, 9, 8, 8, 9, 8, 8, 9, 8, 9, 8, 9, 9, 10, 9, 9, 10, 9, 9, 9, 10, 10, 9, 10, 9, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 10, 10, 10, 10, 10, 11, 10, 11, 10, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11

Offset: 0

Konstantin Knop, May 21 2025

			For n = 0 through n = 5, the fastest is to move n times 1 stone from the origin to the next hole.
For n = 6, one can move two times three stones three holes further, then three times two stones two holes "backwards", therefore a(6) = 2 + 3 = 5. Similarly, for a(3*4 = 12) = 3 + 4 = 7, and a(4*5 = 20) = 4 + 5 = 9. However, for larger oblong numbers, better solutions exist, and a(m*(m+1)) < 2m+1 for m > 4.

Fedor Karpelevitch, Table of n, a(n) for n = 0..113 (terms 0..43 from Fred Lunnon)
Fedor Karpelevitch, Sample solutions for n = 1..113 code here
Fedor Karpelevitch, All solutions (excluding permutations) for n=0..58
Fred Lunnon, A384183 sample solutions

a(n+k) <= a(n) + a(k) <= a(n) + k, for all n, k >= 0. - M. F. Hasler, May 24 2025
a(4k+1) <= 5+a(k+1), a(4k+2) <= 4+a(k+1), a(4k+3) <= 5+a(k+1), a(4k+4) <= 6+a(k+1) for all k > 0. - Konstantin Knop, May 27 2025
a(m^2*k+m) <= 2*m + a(k+1), for all k > 0 and m >= 2. - Yifan Xie, Jun 09 2025

a(11)-a(43) from Max Alekseyev, May 22 2025

A279685 The maximum number of coins that can be processed in n weighings of an adaptive strategy that all are real (and identical) except for one LHR-coin starting in an unknown state.

Original entry on oeis.org

1, 1, 3, 6, 16, 39, 91, 216, 499, 1144, 2651, 6152, 14227, 32904, 76187, 176376, 408179, 944728, 2186779, 5061544, 11715219, 27116008, 62762971, 145270808, 336242675, 778266424, 1801373403, 4169451080, 9650594451, 22337231432, 51701672731

Offset: 0

Tanya Khovanova and Konstantin Knop, Dec 16 2016

An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.

Colin Barker, Table of n, a(n) for n = 0..1000
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (3,-3,5,-4).

Cf. A279673, A279674, A279682, A279684.

Vec((1 - 2*x + 3*x^2 - 5*x^3 + 6*x^4 - 2*x^5 + 4*x^6 + 4*x^7 - 7*x^8 - 4*x^9) / ((1 - x)*(1 - 2*x + x^2 - 4*x^3)) + O(x^40)) \\ Colin Barker, Dec 17 2016

a(n) = (A279673(n-1) + 1)/2 + A279673(n-2), for n > 6.
From Colin Barker, Dec 17 2016: (Start)
a(n) = 3*a(n-1) - 3*a(n-2) + 5*a(n-3) - 4*a(n-4) for n>9.
G.f.: (1 - 2*x + 3*x^2 - 5*x^3 + 6*x^4 - 2*x^5 + 4*x^6 + 4*x^7 - 7*x^8 - 4*x^9) / ((1 - x)*(1 - 2*x + x^2 - 4*x^3)).
(End)

A279684 The maximum number of coins that can be processed in n weighings that all are real except for one LHR-coin starting in the heavy or real state.

Original entry on oeis.org

1, 3, 5, 15, 37, 87, 205, 495, 1173, 2759, 6493, 15263, 35749, 83575, 195181, 455247, 1060533, 2468391, 5740925, 13342975, 30993349, 71956951, 166991501, 387397551, 898427605, 2083016071, 4828379549, 11189823071, 25928070117, 60069313847, 139148806829

Offset: 0

Tanya Khovanova and Konstantin Knop, Dec 16 2016

nonn

An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.

Also the number of outcomes of n weighings that start with a balance and every even-numbered imbalance that is not the last one must be followed by a balance, or every odd-numbered imbalance that is not the last one must be followed by a balance.

			If we have two weighings we are not allowed to have outcomes that consist of two imbalances. That means a(2) = 9 - 4 = 5.
If we have three weighings we are not allowed the following outcomes: <<=, <<<, where any less-than sign can be interchanged with a greater-than sign. Thus a(3) = 27 - 4 - 8 = 15.

Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (3, -1, 1, -2, -8).

Cf. A279673, A279674, A279682, A279685.

I:=[1,3,5,15,37]; [n le 5 select I[n] else 3*Self(n-1)- Self(n-2)+Self(n-3)-2*Self(n-4)-8*Self(n-5): n in [1..40]]; // Vincenzo Librandi, Dec 16 2016

LinearRecurrence[{3, -1, 1, -2, -8}, {1, 3, 5, 15, 37}, 30]

a(n) = 3a(n-1) - a(n-2) + a(n-3) - 2a(n-4) - 8a(n-5).

G.f.: (1 - 3*x^2 + 2*x^3 - 4*x^4)/((1 + x)*(1 - 2*x)*(1 - 2*x + x^2 - 4*x^3)). - Ilya Gutkovskiy, Dec 17 2016

A279682 The maximum number of coins that can be processed in n weighings where all coins are real except for one LHR-coin.

Original entry on oeis.org

1, 3, 9, 19, 49, 123, 297, 707, 1697, 4043, 9561, 22547, 53073, 124571, 291721, 682083, 1592577, 3713643, 8650425, 20132275, 46818225, 108804923, 252718825, 586701827, 1361496929, 3158352139, 7324384281, 16981143379, 39360789521

Offset: 0

Tanya Khovanova and Konstantin Knop, Dec 16 2016

An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.
Also the number of outcomes of n weighings such that every even-numbered imbalance that is not the last one must be followed by a balance or every odd-numbered imbalance that is not the last one must be followed by a balance.
The first seven terms coincide with sequence A102001, which counts all the outcomes that don't have three imbalances in a row.
This sequence also counts the possible outcomes starting in the light or heavy state, and for the coins starting in the real state the possible number of outcomes is a subset for coins starting in the light state.

			Consider a(7): in addition to outcomes that do not have three imbalances in a row, we are not allowed to have any outcomes like <<=<=<<, in which the first (odd-numbered imbalance) and the fourth (even-numbered imbalance) are both followed by an imbalance. We can replace a less-than sign with a greater-than sign. That means a(7) = A102001(7) - 32 = 739 - 32 = 707.

Colin Barker, Table of n, a(n) for n = 0..1000
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (3,-1,1,-2,-8).

Cf. A279673, A279674, A279684, A279685.

I:=[1,3,9,19,49]; [n le 5 select I[n] else 3*Self(n-1)-Self(n-2)+Self(n-3)- 2*Self(n-4)-8*Self(n-5): n in [1..30]]; // Vincenzo Librandi, Dec 18 2016

LinearRecurrence[{3, -1, 1, -2, -8}, {1, 3, 9, 19, 49}, 30]

Vec((1 + x^2 - 6*x^3)/((1 + x)*(1 - 2*x)*(1 - 2*x + x^2 - 4*x^3)) + O(x^40)) \\ Colin Barker, Dec 19 2016

a(n) = 3*a(n-1) - a(n-2) + a(n-3) - 2*a(n-4) - 8*a(n-5).

G.f.: (1 + x^2 - 6*x^3)/((1 + x)*(1 - 2*x)*(1 - 2*x + x^2 - 4*x^3)). - Ilya Gutkovskiy, Dec 17 2016

A279674 The maximum number of coins that can be processed in n weighings that all are real except for one LHR-coin starting in the heavy state.

Original entry on oeis.org

1, 3, 5, 11, 29, 67, 149, 347, 813, 1875, 4325, 10027, 23229, 53731, 124341, 287867, 666317, 1542131, 3569413, 8261963, 19123037, 44261763, 102448341, 237127067, 548852845, 1270371987, 2940399397, 6805838187, 15752764925, 36461289251, 84393166325, 195336103099

Offset: 0

Tanya Khovanova and Konstantin Knop, Dec 16 2016

An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.

Also the number of outcomes of n weighings such that every odd-numbered imbalance that is not the last one must be followed by a balance.

			If we have two weighings we are not allowed to have outcomes that consist of two imbalances. That means a(2) = 9 - 4 = 5.
If we have three weighings we are not allowed the following outcomes: =<<, <<=, <<<, where any less-than sign can be interchanged with a greater-than sign. Thus a(3) = 27 - 2*4 - 8 = 11.

Colin Barker, Table of n, a(n) for n = 0..1000
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (2,-1,4).

Cf. A279673, A279682, A279684, A279685.

I:=[1,3,5]; [n le 3 select I[n] else 2*Self(n-1)-Self(n-2)+4*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Dec 17 2016

LinearRecurrence[{2, -1, 4}, {1, 3, 5}, 30]

Vec((1 + x) / (1 - 2*x + x^2 - 4*x^3) + O(x^40)) \\ Colin Barker, Dec 17 2016

a(n) = 2*a(n-1) - a(n-2) + 4*a(n-3).

G.f.: (1 + x) / (1 - 2*x + x^2 - 4*x^3). - Colin Barker, Dec 17 2016

A279673 The maximum number of coins that can be processed in n weighings where all coins are real except for one LHR-coin starting in the light state.

Original entry on oeis.org

1, 3, 9, 19, 41, 99, 233, 531, 1225, 2851, 6601, 15251, 35305, 81763, 189225, 437907, 1013641, 2346275, 5430537, 12569363, 29093289, 67339363, 155862889, 360759571, 835013705, 1932719395, 4473463369, 10354262163, 23965938537, 55471468387, 128394046889

Offset: 0

Tanya Khovanova and Konstantin Knop, Dec 16 2016

An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.
If an LHR-coin starts in the real state, then the maximum number of coins that can be processed in n weighings is a(n-1).
Also the number of outcomes of n weighings such that every even-numbered imbalance that is not the last one must be followed by a balance.

			If we have three weighings we are not allowed to have outcomes that consist of three imbalances. That means a(3) = 27 - 8 = 19.
If we have four weighings we are not allowed the following outcomes: =<<<, <=<<, <<<=, <<<<, where any less-than sign can be interchanged with a greater-than sign. Thus a(4) = 81 - 3*8 - 16 = 41.

Colin Barker, Table of n, a(n) for n = 0..1000
Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (2,-1,4).

Cf. A279674, A279682, A279684, A279685.

I:=[1,3,9]; [n le 3 select I[n] else 2*Self(n-1)-Self(n-2)+4*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Dec 17 2016

LinearRecurrence[{2, -1, 4}, {1, 3, 9}, 30]

Vec((1 + x + 4*x^2) / (1 - 2*x + x^2 - 4*x^3) + O(x^40)) \\ Colin Barker, Dec 17 2016

a(n) = 2a(n-1) - a(n-2) + 4a(n-3).

G.f.: (1 + x + 4*x^2) / (1 - 2*x + x^2 - 4*x^3). - Colin Barker, Dec 17 2016

A174541 Baron Münchhausen's Sequence.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1

Offset: 1

Tanya Khovanova, Konstantin Knop, and Alexey Radul, Mar 21 2010

Let n coins weighing 1, 2, ..., n grams be given. Suppose Baron Münchhausen knows which coin weighs how much, but his audience does not. Then a(n) is the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.
After a(1) = 0, a(n) is either 1 or 2 for all n.
a(n) = 1 for n triangular, n triangular-plus-one, T_n a square, and T_n a square-plus-one, where T_n is the n-th triangular number; a(n) = 2 for all other n > 1.

			a(7) = 1 because the weighing 1 + 2 + 3 < 7 conclusively demonstrates the weight of the seven-gram coin.

M. Brand, Tightening the bounds on the Baron's Omni-sequence, Discrete Math., 312 (2012), 1326-1335.
Tanya Khovanova, Konstantin Knop and A. Radul, Baron Münchhausen's Sequence, arXiv:1003.3406 [math.CO], 2010.
Tanya Khovanova, Konstantin Knop, and A. Radul, Baron Münchhausen's Sequence, J. Int. Seq. 13 (2010) # 10.8.7.
Tanya Khovanova and A. Radul, Another Coins Sequence

Cf. A000217, A000124, A001108, A072221, A186313.

triangularQ[n_] := IntegerQ[ Sqrt[8n+1]]; a[1] = 0; a[n_ /; triangularQ[n] || triangularQ[n-1] || IntegerQ[ Sqrt[n*(n+1)/2]] || IntegerQ[ Sqrt[n*(n+1)/2 - 1]]] = 1; a[] = 2; Table[a[n], {n, 1, 105}] (* _Jean-François Alcover, Jul 30 2012, after comments *)

;;; The following Scheme program generates terms of Baron
;;; Münchhausen's Sequence.
(define (acceptable? n)
  (or (triangle? n)
      (= n 2)
      (triangle? (- n 1))
      (square? (triangle n))
      (square? (- (triangle n) 1))))
(stream-map
 (lambda (n)
   (if (= n 1)
       0
       (if (acceptable? n)
           1
           2)))
 (the-integers))

A064799 Sum of n-th prime number and n-th composite number.

Original entry on oeis.org

6, 9, 13, 16, 21, 25, 31, 34, 39, 47, 51, 58, 63, 67, 72, 79, 86, 89, 97, 103, 106, 113, 118, 125, 135, 140, 143, 149, 153, 158, 173, 179, 186, 189, 200, 203, 211, 218, 223, 230, 237, 241, 253, 256, 261, 264, 277, 291, 296, 299, 305, 313, 316, 327, 334, 341

Offset: 1

Konstantin Knop, Oct 21 2001

			a(1)=6 because the first prime is 2 and the first composite is 4; 2 + 4 = 6
a(2)=9 because prime(2)=3 and composite(2)=6; 3 + 6 = 9.

Ivan Grischenko, ivansasha(AT)mtu-net.ru, private communication.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A000040, A002808, A171639.

Module[{nn=100,cmps},cmps=Select[Range[nn],CompositeQ];Total/@Thread[{Prime[Range[ Length[ cmps]]],cmps}]] (* Harvey P. Dale, Mar 31 2024 *)

nextComp(n)= { if (!isprime(n), return(n)); return(n + 1) }
{ p=1; c=3; for (n=1, 100, p=nextprime(p + 1); c=nextComp(c + 1); print1(p + c, ", ") ) } \\ Harry J. Smith, Sep 25 2009

from sympy import prime, composite
def A064799(n): return prime(n)+composite(n) # Chai Wah Wu, Aug 30 2021

a(n) = prime(n) + composite(n).
From Jaroslav Krizek, Dec 13 2009: (Start)
a(n) = A000040(n) + A002808(n).
a(n) = A171639(n+1). (End)

More terms from Larry Reeves (larryr(AT)acm.org), Nov 12 2001

Offset changed from 0 to 1 by Harry J. Smith, Sep 25 2009

cp's OEIS Frontend

User: Konstantin Knop

A384183 a(n) = minimum number of steps required to move n stones from a hole to the next one in an infinite row of holes, where at one step we can move any k stones at once from a hole to the hole at distance k to the left or to the right, and there are n stones overall.

Views

Author

Keywords

Examples

Links

Formula

Extensions

A279685 The maximum number of coins that can be processed in n weighings of an adaptive strategy that all are real (and identical) except for one LHR-coin starting in an unknown state.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A279684 The maximum number of coins that can be processed in n weighings that all are real except for one LHR-coin starting in the heavy or real state.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A279682 The maximum number of coins that can be processed in n weighings where all coins are real except for one LHR-coin.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A279674 The maximum number of coins that can be processed in n weighings that all are real except for one LHR-coin starting in the heavy state.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A279673 The maximum number of coins that can be processed in n weighings where all coins are real except for one LHR-coin starting in the light state.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A174541 Baron Münchhausen's Sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs