A058992 - OEIS

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?

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, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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

REFERENCES

R. Tijdeman, On a telephone problem, Nieuw Arch. Wisk. (3) 19 (1971), 188-192. Math. Rev. 49 #7151

LINKS

T. D. Noe, Table of n, a(n) for n = 1..1000

Brenda Baker and Robert Shostak, Gossips and Telephones, Discrete Mathematics 2 (1972) 191-193. Math. Rev. 46 # 68.

Richard T. Bumby, A problem with telephones, SIAM J. Alg. Disc. Meth., Vol. 2, Iss. 1 (1981), pp. 13-18. Math. Rev. 82f:05083.

A. Hajnal, E. C. Milner, and E. Szemeredi, A cure for the telephone disease, Canad. Math. Bull., Vol. 15 (3) (1972), pp. 447-450. Math. Rev. 47 #3184.

D. J. Kleitman and J. B. Shearer, Further Gossip Problems, Discrete Mathematics, Vol. 30, Iss. 2 (1980), pp. 151-156. Math. Rev. 81d:05068.

Torsten Sillke, References.

Torsten Sillke, Proofs.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

FORMULA

a(n) = 2*n - 4 for n >= 4.

G.f.: x^2*(1+x-x^2+x^3)/(1-x)^2. - Colin Barker, Jun 07 2012

E.g.f.: 2*(x - 2)*exp(x) + 4 + 2*x + x^2/2 + x^3/6. - Elmo R. Oliveira, Sep 17 2025

MATHEMATICA

Join[{0, 1, 3}, NestList[#+2&, 4, 60]] (* Harvey P. Dale, Apr 01 2012 *)

PROG

(PARI) a(n)=if(n>3, 2*n-4, [0, 1, 3][n]) \\ Charles R Greathouse IV, Feb 10 2017