login
Number of days required to spread gossip to n people.
7

%I #22 Jun 17 2022 12:26:02

%S 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,

%T 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,

%U 8,7,8,7,8,7,8,7,8,7,8,7,8,7,8,7,8,7,8

%N Number of days required to spread gossip to n people.

%C 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.

%C a(A240277(n)) = n and a(m) < n for m < A240277(n). - _Reinhard Zumkeller_, Apr 03 2014

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

%H T. D. Noe, <a href="/A007456/b007456.txt">Table of n, a(n) for n = 1..10000</a>

%H C. Kenneth Fan, Bjorn Poonen and George Poonen, <a href="http://www.jstor.org/stable/2691050">How to spread rumors fast</a>, Mathematics Magazine 70 (Feb, 1997), pp. 40-42.

%H I. Peterson, <a href="https://web.archive.org/web/20130702062252/http://www.maa.org/mathland/mathland_3_17.html">Spreading Rumors</a>, MathLand, March 17, 1997.

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

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

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

%o (Haskell)

%o a007456 1 = 0

%o a007456 n = a000523 (n - 1) + mod n 2 + 1

%o -- _Reinhard Zumkeller_, Apr 03 2014

%Y Cf. A160464, A043529.

%Y Cf. A000523.

%K nonn,nice,easy

%O 1,3

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

%E More terms from _David W. Wilson_

%E Formulae corrected by _Johannes W. Meijer_, May 15 2009