|
|
A007456
|
|
Number of days required to spread gossip to n people.
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
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.
|
|
REFERENCES
|
D. Shasha, Gossiping Defenders, The Puzzling Adventures of Dr. Ecco, pp. 62-4;156 W. H. Freeman NY 1988.
|
|
LINKS
|
|
|
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
|
|
MATHEMATICA
|
Join[{0}, Table[Floor[Log[2, n - 1]] + Mod[n - 2, 2] + 1, {n, 2, 100}]] (* T. D. Noe, Mar 16 2012 *)
|
|
PROG
|
(Haskell)
a007456 1 = 0
a007456 n = a000523 (n - 1) + mod n 2 + 1
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
Alex Graesser (AlexG(AT)sni.co.za)
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|