Programming Challenges
March 21st, 2018 at 3:58:23 PM
permalink
Quote: gamerfreakHere is a fun one:
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
I think you actually don't need code but can use logic to derive the correct result. The program I wrote confirms this.
The easiest way I could think was to pick i=numerator and evaluate a number j=floor(7/3*numerator), then look at i/j (actually I looked at a few more either way). This gives 428570/999997 as the closest.
Alternative thought.
It transpires that 428571/999999 = 3/7.
428570/(999996 2/3) = 3/7 - so 428570/999997 is close and less.
428569/(999994 1/3) = 3/7 - but 428569/999995 is not so close as above
428568/999992 = 3/7 - so reduces to 3/7.
Thus there are three series of interesting numbers.
3x/7x
(3x+1)/(7x+3)
(3x+2)/(7x+4)
It follows that the nearest would be last of these and larger x's get closer and closer to 3/7.
The program looks for a larger value than one already seen, and after 2/5 puts out an entry every time the denominator increases by 7.
Alternative thought.
It transpires that 428571/999999 = 3/7.
428570/(999996 2/3) = 3/7 - so 428570/999997 is close and less.
428569/(999994 1/3) = 3/7 - but 428569/999995 is not so close as above
428568/999992 = 3/7 - so reduces to 3/7.
Thus there are three series of interesting numbers.
3x/7x
(3x+1)/(7x+3)
(3x+2)/(7x+4)
It follows that the nearest would be last of these and larger x's get closer and closer to 3/7.
The program looks for a larger value than one already seen, and after 2/5 puts out an entry every time the denominator increases by 7.
March 21st, 2018 at 5:58:29 PM
permalink
This does sound like an AIME problem, more than a programming one.
Still...
1,000,000: 428570 / 999997
2,000,000: 857141 / 1999996
3,000,000: 1285712 / 2999995
4,000,000: 1714283 / 3999994
5,000,000: 2142857 / 5000000
6,000,000: 2571428 / 5999999
7,000,000: 2999999 / 6999998
8,000,000: 3428570 / 7999997
9,000,000: 3857141 / 8999996
10,000,000: 4285712 / 9999995
11,000,000: 4714283 / 10999994
12,000,000: 5142857 / 12000000
13,000,000: 5571428 / 12999999
14,000,000: 5999999 / 13999998
15,000,000: 6428570 / 14999997
16,000,000: 6857141 / 15999996
17,000,000: 7285712 / 16999995
18,000,000: 7714283 / 17999994
19,000,000: 8142857 / 19000000
20,000,000: 8571428 / 19999999
21,000,000: 8999999 / 20999998
22,000,000: 9428570 / 21999997
23,000,000: 9857141 / 22999996
24,000,000: 10285712 / 23999995
25,000,000: 10714283 / 24999994
26,000,000: 11142857 / 26000000
27,000,000: 11571428 / 26999999
28,000,000: 11999999 / 27999998
29,000,000: 12428570 / 28999997
30,000,000: 12857141 / 29999996
31,000,000: 13285712 / 30999995
32,000,000: 13714283 / 31999994
33,000,000: 14142857 / 33000000
34,000,000: 14571428 / 33999999
35,000,000: 14999999 / 34999998
36,000,000: 15428570 / 35999997
37,000,000: 15857141 / 36999996
38,000,000: 16285712 / 37999995
39,000,000: 16714283 / 38999994
40,000,000: 17142857 / 40000000
41,000,000: 17571428 / 40999999
42,000,000: 17999999 / 41999998
43,000,000: 18428570 / 42999997
44,000,000: 18857141 / 43999996
45,000,000: 19285712 / 44999995
46,000,000: 19714283 / 45999994
47,000,000: 20142857 / 47000000
48,000,000: 20571428 / 47999999
49,000,000: 20999999 / 48999998
50,000,000: 21428570 / 49999997
51,000,000: 21857141 / 50999996
52,000,000: 22285712 / 51999995
53,000,000: 22714283 / 52999994
54,000,000: 23142857 / 54000000
55,000,000: 23571428 / 54999999
56,000,000: 23999999 / 55999998
57,000,000: 24428570 / 56999997
58,000,000: 24857141 / 57999996
59,000,000: 25285712 / 58999995
60,000,000: 25714283 / 59999994
61,000,000: 26142857 / 61000000
62,000,000: 26571428 / 61999999
63,000,000: 26999999 / 62999998
64,000,000: 27428570 / 63999997
65,000,000: 27857141 / 64999996
66,000,000: 28285714 / 66000000
67,000,000: 28714283 / 66999994
68,000,000: 29142857 / 68000000
69,000,000: 29571428 / 68999999
70,000,000: 29999999 / 69999998
71,000,000: 30428570 / 70999997
72,000,000: 30857141 / 71999996
73,000,000: 31285712 / 72999995
74,000,000: 31714283 / 73999994
75,000,000: 32142857 / 75000000
76,000,000: 32571428 / 75999999
77,000,000: 32999999 / 76999998
78,000,000: 33428570 / 77999997
79,000,000: 33857141 / 78999996
80,000,000: 34285712 / 79999995
81,000,000: 34714283 / 80999994
82,000,000: 35142857 / 82000000
83,000,000: 35571428 / 82999999
84,000,000: 35999999 / 83999998
85,000,000: 36428570 / 84999997
86,000,000: 36857141 / 85999996
87,000,000: 37285712 / 86999995
88,000,000: 37714283 / 87999994
89,000,000: 38142857 / 89000000
90,000,000: 38571428 / 89999999
91,000,000: 38999999 / 90999998
92,000,000: 39428570 / 91999997
93,000,000: 39857141 / 92999996
94,000,000: 40285712 / 93999995
95,000,000: 40714283 / 94999994
96,000,000: 41142857 / 96000000
97,000,000: 41571428 / 96999999
98,000,000: 41999999 / 97999998
99,000,000: 42428570 / 98999997
100,000,000: 42857141 / 99999996
Comparing 42857141 / 99999996 to 3/7:
0.428571427142857
0.428571428571429
Still...
1,000,000: 428570 / 999997
2,000,000: 857141 / 1999996
3,000,000: 1285712 / 2999995
4,000,000: 1714283 / 3999994
5,000,000: 2142857 / 5000000
6,000,000: 2571428 / 5999999
7,000,000: 2999999 / 6999998
8,000,000: 3428570 / 7999997
9,000,000: 3857141 / 8999996
10,000,000: 4285712 / 9999995
11,000,000: 4714283 / 10999994
12,000,000: 5142857 / 12000000
13,000,000: 5571428 / 12999999
14,000,000: 5999999 / 13999998
15,000,000: 6428570 / 14999997
16,000,000: 6857141 / 15999996
17,000,000: 7285712 / 16999995
18,000,000: 7714283 / 17999994
19,000,000: 8142857 / 19000000
20,000,000: 8571428 / 19999999
21,000,000: 8999999 / 20999998
22,000,000: 9428570 / 21999997
23,000,000: 9857141 / 22999996
24,000,000: 10285712 / 23999995
25,000,000: 10714283 / 24999994
26,000,000: 11142857 / 26000000
27,000,000: 11571428 / 26999999
28,000,000: 11999999 / 27999998
29,000,000: 12428570 / 28999997
30,000,000: 12857141 / 29999996
31,000,000: 13285712 / 30999995
32,000,000: 13714283 / 31999994
33,000,000: 14142857 / 33000000
34,000,000: 14571428 / 33999999
35,000,000: 14999999 / 34999998
36,000,000: 15428570 / 35999997
37,000,000: 15857141 / 36999996
38,000,000: 16285712 / 37999995
39,000,000: 16714283 / 38999994
40,000,000: 17142857 / 40000000
41,000,000: 17571428 / 40999999
42,000,000: 17999999 / 41999998
43,000,000: 18428570 / 42999997
44,000,000: 18857141 / 43999996
45,000,000: 19285712 / 44999995
46,000,000: 19714283 / 45999994
47,000,000: 20142857 / 47000000
48,000,000: 20571428 / 47999999
49,000,000: 20999999 / 48999998
50,000,000: 21428570 / 49999997
51,000,000: 21857141 / 50999996
52,000,000: 22285712 / 51999995
53,000,000: 22714283 / 52999994
54,000,000: 23142857 / 54000000
55,000,000: 23571428 / 54999999
56,000,000: 23999999 / 55999998
57,000,000: 24428570 / 56999997
58,000,000: 24857141 / 57999996
59,000,000: 25285712 / 58999995
60,000,000: 25714283 / 59999994
61,000,000: 26142857 / 61000000
62,000,000: 26571428 / 61999999
63,000,000: 26999999 / 62999998
64,000,000: 27428570 / 63999997
65,000,000: 27857141 / 64999996
66,000,000: 28285714 / 66000000
67,000,000: 28714283 / 66999994
68,000,000: 29142857 / 68000000
69,000,000: 29571428 / 68999999
70,000,000: 29999999 / 69999998
71,000,000: 30428570 / 70999997
72,000,000: 30857141 / 71999996
73,000,000: 31285712 / 72999995
74,000,000: 31714283 / 73999994
75,000,000: 32142857 / 75000000
76,000,000: 32571428 / 75999999
77,000,000: 32999999 / 76999998
78,000,000: 33428570 / 77999997
79,000,000: 33857141 / 78999996
80,000,000: 34285712 / 79999995
81,000,000: 34714283 / 80999994
82,000,000: 35142857 / 82000000
83,000,000: 35571428 / 82999999
84,000,000: 35999999 / 83999998
85,000,000: 36428570 / 84999997
86,000,000: 36857141 / 85999996
87,000,000: 37285712 / 86999995
88,000,000: 37714283 / 87999994
89,000,000: 38142857 / 89000000
90,000,000: 38571428 / 89999999
91,000,000: 38999999 / 90999998
92,000,000: 39428570 / 91999997
93,000,000: 39857141 / 92999996
94,000,000: 40285712 / 93999995
95,000,000: 40714283 / 94999994
96,000,000: 41142857 / 96000000
97,000,000: 41571428 / 96999999
98,000,000: 41999999 / 97999998
99,000,000: 42428570 / 98999997
100,000,000: 42857141 / 99999996
Comparing 42857141 / 99999996 to 3/7:
0.428571427142857
0.428571428571429
March 27th, 2018 at 1:24:57 PM
permalink
Quote: charliepatrickI think you actually don't need code but can use logic to derive the correct result.
Quote: ThatDonGuyThis does sound like an AIME problem, more than a programming one.
Still...
I'm pulling from project euler, where they are intended to be solved with a combination of math/programming .... but it seems like you guys keep out mathing the easier problems.
Should I pull a much harder one?
March 27th, 2018 at 1:30:33 PM
permalink
This one is interesting (and I think much harder, starting it now)...
You are given a unique investment opportunity.
Starting with $1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.
Your return is double your bet for heads and you lose your bet for tails.
For example, if f = 1/4, for the first toss you bet $0.25, and if heads comes up you win $0.5 and so then have $1.5. You then bet $0.375 and if the second toss is tails, you have $1.125.
Choosing f to maximize your chances of having at least $1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?
Starting with $1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.
Your return is double your bet for heads and you lose your bet for tails.
For example, if f = 1/4, for the first toss you bet $0.25, and if heads comes up you win $0.5 and so then have $1.5. You then bet $0.375 and if the second toss is tails, you have $1.125.
Choosing f to maximize your chances of having at least $1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?
