Since the early civilizations, humankind has enjoyed games of chance. Even the ingenious Greeks, known for their groundbreaking concept of the least common multiple (LCM), couldn’t resist a good gamble.

Inspired by this mathematical marvel, folks in Athens devised a unique betting system: after purchasing a ticket, a participant would receive a random number of coins. To determine this number, there are N ≥ 3 ordered slots numbered from 1 to N. A token is initially placed at slot 1, and the following steps are repeated:

Let x be the number of the slot where the token is currently located.
Generate a random integer y between 1 andN, and compute z the LCM of x and y.
If z > N, the procedure ends.
Otherwise, the token is moved to slot z, and the participant receives one coin.

As it is well known, the house always wins: the casino employs a particular probability distribution for generating random integers, so as to ensure a profitable outcome.

The casino owner is constantly seeking to optimize the betting system’s profitability. You, an AI designed to aid in such tasks, are given N and the probability distribution. Determine the expected total number of coins awarded to a participant.

#6351 upload - done - how_to_reg - auto_awesome Special judge

Greek Casino timer 1s memory 1024MB

#6351
Special judge

Greek Casino 1s 1024MB