cp's OEIS Frontend

A058992 Gossip Problem: there are n people and each of them knows some item of gossip not known to the others. They communicate by telephone and whenever one person calls another, they tell each other all that they know at that time. How many calls are required before each gossip knows everything?

%I A058992 #51 Feb 11 2025 02:29:20
%S A058992 0,1,3,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,
%T A058992 48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,
%U A058992 94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124
%N A058992 Gossip Problem: there are n people and each of them knows some item of gossip not known to the others. They communicate by telephone and whenever one person calls another, they tell each other all that they know at that time. How many calls are required before each gossip knows everything?
%C A058992 The sequence (for n>=1) refers to the famous "nine dots puzzle" as well. It represents the minimum number of straight lines that you need to fit the centers of n^2 dots (without lifting the pencil from the paper). - _Marco Ripà_, Apr 01 2013
%D A058992 R. Tijdeman, On a telephone problem. Nieuw Arch. Wisk. (3) 19 (1971), 188-192. Math. Rev. 49 #7151
%H A058992 T. D. Noe, <a href="/A058992/b058992.txt">Table of n, a(n) for n = 1..1000</a>
%H A058992 B. Baker and R. Shostak, <a href="https://doi.org/10.1016/0012-365X(72)90001-5">Gossips and Telephones</a>, Discrete Mathematics 2 (1972) 191-193. Math. Rev. 46 # 68.
%H A058992 R. T. Bumby, <a href="https://doi.org/10.1137/0602002">A problem with telephones</a>, SIAM J. Alg. Disc. Meth. 2 (1981) 13-18. Math. Rev. 82f:05083.
%H A058992 A. Hajnal, E. C. Milner and E. Szemeredi, <a href="http://dx.doi.org/10.4153/CMB-1972-081-0">A cure for the telephone disease</a>, Canad. Math. Bull. 15 (1972), 447-450. Math. Rev. 47 #3184.
%H A058992 D. J. Kleitman and J. B. Shearer, <a href="https://doi.org/10.1016/0012-365X(80)90116-8">Further Gossip Problems</a>, Discrete Mathematics 30 (1980), 151-156. Math. Rev. 81d:05068.
%H A058992 T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/gossip">References</a>
%H A058992 T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf">Proofs</a>
%H A058992 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F A058992 a(n) = 2n - 4 for n >= 4.
%F A058992 G.f.: x^2*(1+x-x^2+x^3)/(1-x)^2. - _Colin Barker_, Jun 07 2012
%t A058992 Join[{0,1,3}, NestList[#+2&,4,60]] (* _Harvey P. Dale_, Apr 01 2012 *)
%o A058992 (PARI) a(n)=if(n>3, 2*n-4, [0,1,3][n])  \\ _Charles R Greathouse IV_, Feb 10 2017
%Y A058992 Cf. A007456.
%K A058992 easy,nonn,nice
%O A058992 1,3
%A A058992 Torsten Sillke (torsten.sillke(at)lhsystems.com), Jan 17 2001