| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
A few months ago I started my own network. At first I was the only
person on it, but after a couple of days I convinced a friend to
join the network also. A few days later, another friend had joined.
By then my first friend had also gotten a friend of his to join,
and so it went.
After several weeks, I began to notice something odd. It had taken
me 2 days to recruit my first new node, then 3 more days to
recruit my second, then 5 more for my third, 7 more for the next,
and so on. Likewise my first friend had taken 2 days for his first
recuition, 3 more for the next, et cetera. In other words we were
each taking the n-th prime days to recruit our (individual) n-th new
node.
Now assuming that we all continue at this rate, and assuming that
I started on Jan 1 1986, and assuming that there is a constant 1
billion people in the world, and ignoring implementation details
like availibilty of phone lines, cost of nodes, production limits
on microvaxes, et cetera:
A) How many nodes do I have today?
B) On what date will everyone in the world have their own node
on our network?
-- Barry
Note: To the best of my knowledge, this is a new problem of unknown
difficulty, though I feel sure that it would yield to brute force
methods.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 556.1 | CLT::GILBERT | eager like a child | Thu Aug 07 1986 14:40 | 93 | |
program network (input, output);
type
p_user_info = ^user_info;
user_info = record
next: p_user_info;
day,
users,
prime: integer;
end;
var
root: p_user_info;
people: integer;
function is_prime (p: integer): boolean;
var z: integer;
begin
if p = 2 then is_prime := true
else if not odd(p) then is_prime := false
else
begin
z := 1;
repeat z := z + 2 until (z*z > p) or ((p mod z) = 0);
is_prime := (z*z > p);
end;
end;
function next_prime (p: integer): integer;
var q: integer;
begin
q := p + 1;
if not odd(q) then q := q + 1;
while not is_prime(q) do q := q + 2;
next_prime := q;
end;
procedure insert_sub (p: p_user_info; var root: p_user_info);
begin
if (root = nil) or (p^.day <= root^.day)
then
begin
p^.next := root;
root := p;
end
else
insert_sub (p, root^.next);
end;
procedure insert (p: p_user_info);
begin
p^.day := p^.day + p^.prime;
p^.prime := next_prime (p^.prime);
insert_sub (p, root);
end;
procedure new_users (users,day: integer);
var p: p_user_info;
begin
if users <> 0 then
begin
new(p);
p^.day := day;
p^.users := users;
p^.prime := 2;
people := people + users;
insert (p);
end;
end;
procedure main;
var day, news: integer;
p: p_user_info;
begin
new_users (1, 0); { One person on day 0 }
for day := 0 to 100 do
begin
news := 0;
while root^.day = day do
begin
p := root; root := p^.next; { Remove from the list }
news := news + p^.users;
insert (p);
end;
new_users (news, day);
writeln (people, ' users on day ', day);
end;
end;
begin
root := nil;
people := 0;
main;
end.
| |||||