A089645 Penny Flipping, or Flipping Coins: Given a stack of n coins, flip the top coin, then the stack of the top two coins, then the stack of the top three etc... starting again with the top coin after flipping all n coins. A flip of m coins reverses their order and inverts their state. This is the number of flips required to restore the stack to its original configuration.

2, 3, 9, 11, 24, 35, 28, 31, 80, 60, 121, 119, 116, 195, 75, 79, 204, 323, 228, 199, 146, 264, 529, 504, 200, 675, 540, 251, 840, 899, 186, 191, 1088, 748, 1225, 324, 740, 1140, 1521, 1079, 1680, 336, 1204, 484, 540, 460, 1692, 1151, 734, 2499

Offset: 1

Author

Richard Forster (gbrl01(AT)yahoo.co.uk), Jan 02 2004

Keywords

• easy
• nonn
• nice

Comments

Here "original configuration" seems to mean each coin in original orientation and either original or reverse order; for the original order and either original or reverse orientation n*A002326(n) flips required, while for both original order and original orientation n*A003558(n) required. - Henry Bottomley, Jan 19 2007

Birtwistle (1973) attributes the problem to Iain Bride and John Gilder of UMIST (University of Manchester Institute of Science and Technology).

Examples

			For 3 coins (starting with HHH) the flips move the stack through the sequence: HHH -1-> THH -2-> THH -3-> TTH -1-> HTH -2-> HTH -3-> THT -1-> HHT -2-> TTT -3-> HHH. (-n-> indicates n coins are flipped)
		

References

• G. M. Birtwistle, Simula Begin, Auerbach Publishers, Philadelphia, 1973 [Uses this problem to illustrate the power of the Simula language]
• Popular Computing (Calabasas, CA), Penny Flipping, Vol. 3 (No. 23, Feb 1973), pages PC23-10 to PC23-13) and Vol. 3 (No. 29, Aug 1975), pages PC29-6 to PC29-8. Gives first 32 terms.

Links

• B. B. Newman, The Flippin' Coins Problem, Mathematics Magazine, Vol. 54 (1981), pp. 51-59.

Crossrefs

Cf. A002326, A003558, A056951.

Programs

Mathematica

b[n_] := MultiplicativeOrder[2, 2n+1];
c[n_] := MultiplicativeOrder[2, 2n+1, {-1, 1}];
a[1] = 2; a[n_] := If[b[n] == c[n], n*b[n], n*b[n]/2 - 1];
Array[a, 50] (* Jean-François Alcover, Oct 29 2017, after Henry Bottomley *)

Formula

For n>1, if A002326(n)=A003558(n) then a(n)=n*A002326(n), otherwise a(n)=n*A002326(n)-1. - Henry Bottomley, Jan 19 2007