n people know each a different piece of gossip.

They can phone each other and exchange all they know so that after the call the parties know anything that either of them knew before the call.

What is the smallest number of calls needed so that everyone knows everything and how is this number achieved?

(In reply to re(2): solution, some doubts by Steve Herman)

It appears that the number of calls needed matches the integer sequence: OLEIS A047544 - Numbers that are congruent to {1,3,4,7} mod 8.

OFFSET: 1,2

1, 3, 4, 7, 9, 11, 12, 15, 17, 19, 20, 23, 25, 27, 28, 31, 33, 35, 36, 39, 41, 43, 44, 47, 49, 51, 52, 55, 57, 59, 60, 63, 65, 67, 68, 71, 73, 75, 76, 79, 81, 83, 84, 87, 89, 91, 92, 95, 97, 99, 100, 103, 105, 107, 108 ...

Posted by Dej Mar on 2012-07-27 15:29:18