Problem 186

[mathguy314]

For 99% of the users to be in the PM's network of friends, does this mean 990,000 users including the PM, or 990,000 users not including the PM (so the network contains 990,001 users)? Either way, I seem to be getting the wrong answer, so is there another interpretation? For example, should the network contain 99% of all successful callers, not 99% of the subscribers?

To help me verify my algorithms, can someone give me the answer if everything were reduced modulo 1000? The PM's number would then be 287.

[stijn263]

990,000 users including the PM. It wasn't clear to me either, so I just tried both values.

I got quite a few overflow bugs calculating the s[k], so that might be the problem?

modulo 1000 I get:
2234
as the lowest value for which the PM is in a network with 990 users including the PM.

[mathguy314]

Yep, overflow bug. And I thought I checked for that, after it having bit me several times before on other problems. Thanks for the help.

[quilan]

............. I could have been the 3'rd one to solve it, but I've had an off-by-one bug with my Sk generator for the last two days. Unbelievable.

[WR]

Just to verify that my generator works, could somebody please tell me whether S(3681161) = 910544 is correct?

[daniel.is.fischer]

Yes, that's what I get, too.

[WR]

Thanks for the quick response.

This is a funny problem! In the last two weeks I had solutions ranging from sol-3 to sol+8, but not the correct one. And - after reading the posts in the forum - I noticed I've not even really understood the problem!

[Rawling]

Just to verify that my generator works, could somebody please tell me whether S(3681161) = 910544 is correct?

Thanks WR, this is exactly what I needed. I wasn't getting the right answer but of couse assumed it was my algorithm rather than the ("trivial) generator.

Nice problem; surprised more people haven't solved it.

[Perlkonig]

Just to verify that my generator works, could somebody please tell me whether S(3681161) = 910544 is correct?

Thanks WR, this is exactly what I needed. I wasn't getting the right answer but of couse assumed it was my algorithm rather than the ("trivial) generator.

Perhaps this falls under the rubric of "partial answers to problems," but I thought I'd ask.

The generator is giving me nothing but trouble. I'm not getting the same number as above, regardless of the two ways I try it. Can somebody confirm if the generator for k>55 is recursive or just retrospective? By this I mean, for a large value of k (like 3681161) do I calculate k-24 by continually subtracting 24 from k until I get a number less than 56? Or do I keep track of past values of S(k) and just go back in that list 24 spots? Either way, I still don't get the same number for k=3681161. My understanding is that Python integers are arbitrary precision, so I shouldn't be having overflow problems.

Any insight would be appreciated. Thanks!

[thundre]

for a large value of k (like 3681161) do I calculate k-24 by continually subtracting 24 from k until I get a number less than 56?

No.

Or do I keep track of past values of S(k) and just go back in that list 24 spots?

Yes.
Go back 24 spots and 55 spots, add those two together, and take the modulo.

[anantkaushik89]

Hello all, I am not able to understand one thing. I listed the values for records 1 to 1000000. But I am not able to see the PM's number there. I can see that when I double the list? So does this mean I need to find the calls for 99% users from the bigger set or the original set? Or am I doing something wrong and I should see the PM's number in the first million records.

[Georg]

Hello all, I am not able to understand one thing. I listed the values for records 1 to 1000000. But I am not able to see the PM's number there. I can see that when I double the list?

This is correct. This is an infinite list and you should count the successful calls, ...

[anantkaushik89]

Hello Georg, thank you so much for replying. This does clear one doubt. But one confusion is that do we need to count the successful calls in the 99% of the first one million records? Because one confusion for me is that where do I need to end the list, and what is the 99% which is being referred to?

[DJohn]

It's 99% of the one million users. The list of calls is infinite. You're asked how much of that infinite list you need to look at before 99% of the users are connected to the PM (either directly or indirectly).

For example, suppose there are five users, and the calls go

Code: Select all

(misdial) 4,4
1: 1,4
2: 2,4
(misdial) 3,3
(misdial) 1,1
3: 5,4
4: 3,2
(misdial): 2,2
5: 3,4

After the first two successful calls, user 5 is still not connected to anyone. After the third, they are connected to users 4 (directly, because of call 3), 1 (because 1 is connected to 4 by call 1), 2 (because 2 is connected to 4 by call 2), and 5 (because 4 is a friend of 5, and 5 is a friend of 4, that makes 5 a friend of a friend of 5). At this point, user 5 is connected to 4 out of the 5 users, which is 80%.

If we were asked how many successful calls it took for user 5 to be connected to 80% of the users, the answer would be 3.

[enigmaticcam]

I misunderstood this problem. It's obvious from the generator that at most you can have 1,000,000 users. But the problem description says, "After how many successful calls, not counting misdials, will 99% of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?" I had assumed this meant, not all the users, but rather the users you've found up to a certain point. That was several hours wasted when I had it all along

Do you think it makes sense to say "99% of all users", or "99% of the possible 1,000,000 users"?

[hk]

I think you overlooked the very first sentence of the problem:
'Here are the records from a busy telephone system with one million users:'

[enigmaticcam]

I guess I did, thanks. Sorry about that