A007456 Number of days required to spread gossip to n people.

0, 1, 3, 2, 4, 3, 4, 3, 5, 4, 5, 4, 5, 4, 5, 4, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 7, 6, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8

Offset: 1

Author

Alex Graesser (AlexG(AT)sni.co.za)

Keywords

• nonn
• nice
• easy

Comments

On the first day, each gossip has his own tidbit. On each successive day, disjoint pairs of gossips may share tidbits (over the phone). After a(n) days, all gossips have all tidbits.

a(A240277(n)) = n and a(m) < n for m < A240277(n). - Reinhard Zumkeller, Apr 03 2014

References

• D. Shasha, Gossiping Defenders, The Puzzling Adventures of Dr. Ecco, pp. 62-4;156 W. H. Freeman NY 1988.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• C. Kenneth Fan, Bjorn Poonen and George Poonen, How to spread rumors fast, Mathematics Magazine 70 (Feb, 1997), pp. 40-42.
• I. Peterson, Spreading Rumors, MathLand, March 17, 1997.

Crossrefs

Cf. A160464, A043529.

Cf. A000523.

Programs

Haskell

a007456 1 = 0
a007456 n = a000523 (n - 1) + mod n 2 + 1
-- Reinhard Zumkeller, Apr 03 2014

Mathematica

Join[{0}, Table[Floor[Log[2, n - 1]] + Mod[n - 2, 2] + 1, {n, 2, 100}]] (* T. D. Noe, Mar 16 2012 *)

Formula

a(1) = 0; for n >= 2, a(n) = floor(log_2(n-1)) + ((n-2) mod 2) + 1.

G.f.: -1 + (1/(1-z))*(1/(1+z) + Sum_{k>=0} z^(2^k)). - Ralf Stephan, Apr 06 2003

Extensions

More terms from David W. Wilson

Formulae corrected by Johannes W. Meijer, May 15 2009