# Challenge Math Challenge - March 2019

• Featured

#### fresh_42

Mentor
2018 Award
Yes I started from arbitrary (any) a/b ...
You did not:
Let choose arbitrary rational number a/b so that Greatest Common Divisor GCD(a,b)=1
If is not in cancelled form repeating "the algorithm" in one moment I will get a=b > 1
I have no idea how this would happen.

#### Bosko

Gold Member
I have no idea how this would happen.
It is all about Greatest Common Divisor algorithm
Example you want to find GDC(20,12)
20 , 12
20-12 -> 8 , 12
8, 12-8->4
8-4->4 , 4
4=4 -> STOP
Explanation is that if x divides a and b then it also divides a-b
"Just repeat subtracting the smaller from the bigger one until they are both equal."
P.S. I studied Math for Computer Sciences. This is the way how computers find GCD

Last edited:

#### QuantumQuest

Gold Member
I was not aware of this but in any case, although Wikipedia has a more elegant proof, I was mainly looking for a proof that includes definitions and some geometrical thinking without of course excluding any other solution.

#### fbs7

Trying high-school 5a

Running a simple search algorithm. 1st column are the available digits, 2nd column is n, 3rd column is 2n; algorithm always chooses the lowest digit alvailable for the left-most available digit in n (because we want the minimum numbers), and then backtracks if any digit repeated. Solution is 06729 13458.

I bet there's a more elegant solution to this, but I'm a programmer

Code:
0123456789 abcde fghik, try a in 0123456789
.123456789 0bcde 0ghik,   bcde <= 4999, rejected repeat 0
..23456789 0bcde 1ghik,   bcde >= 5000, try b in 56789, tried 5
..234.6789 05cde 10hik,     cde <= 499, rejected repeat 0
..234.6789 05cde 11hik,     cde >= 500, rejected repeat 1
...345.789 06cde 12hik,     cde <= 499, try c in 34, tried 34
....45.789 063de 126ik,       de <= 499, rejected repeat 6
....45..89 063de 127ik,       de >= 500, try d in 89, tried 89
....4...89 0635e 1270k,         e <= 4, rejected repeat 0
....4...89 0635e 1271k,         e >= 5, rejected repeat 1
....45...9 0638e 1276k,         e <= 4, rejected repeat 6
....45...9 0638e 1277k,         e >= 5, rejected repeat 7
....45.... 0639e 1278k,         e <= 4, try e in 45, tried 45
.....5.... 06394 12788,           rejected repeat 8
....45..8. 0639e 1279k,         e >= 5, rejected repeat 9
...3.5.7.9 064de 128ik,       de <= 49, try d in 3, tried 3
.....5.7.9 0643e 1286k,         e <= 4, rejected repeat 6
.....5...9 0643e 1287k,         e >= 5, try e in 59, tried 59
.......... 06435 12870,           rejected repeat 0
.......... 06439 12878,           rejected repeat 8
...3.5.78. 064de 129ik,       de >= 50, try d in 578, tried 5
...3...78. 0645e 1290k,         e <= 4, rejected repeat 0
...3...78. 0645e 1291k,         e >= 5, rejected repeat 1
...3.5..8. 0647e 1294k,         e <= 4, rejected repeat 4
...3....8. 0647e 1295k,         e >= 5, tried e in 8, tried 8
........8. 06478 12956,         e >= 5, rejected repeat 6
...3.5.7.. 0648e 1296k,         e <= 4, rejected repeat 6
...3.5.... 0648e 1297k,         e >= 5, tried e in 5, tried 5
...3...... 06485 12970,           rejected repeat 0
..2.45.789 06cde 13hik,     cde >= 500, trying c in 5789
..2.4..789 065de 130ik,       de <= 49, rejected repeat 0
..2.4..789 065de 131ik,       de >= 50, rejected repeat 1
..2..5..89 067de 134ik,       de <= 49, trying d in 2
.....5..89 0672e 1344k,         e <= 4, rejected repeat 4
........89 0672e 1345k,         e >= 5
.......... 06729 13458,           stop

#### fresh_42

Mentor
2018 Award
I bet there's a more elegant solution to this, but I'm a programmer
No, problem! Programmers can learn something, too, we serve all!

Your solution doesn't contain the cipher $0$. A leading zero is commonly not considered to be a digit of a number.
And now to my promise:
• Should I have mentioned this?
Yes and no. Yes, if I wanted to write a detailed concept for your program. No, since this is all you get normally: a description in common English, usually far more vague than question #5.

Yes. It is part of every programming process to close the gap between "We need a solution!" and final user and code. And there are several steps in between: problem description, doability study, rough concept, detailed concept, database architecture, e.g. ORD, tests and reviews, final approval, implementation and some minor ones in between.

• Can I read code or output?
Not really. It's lousy commentated.

• A propos output! Shouldn't you deliver an executable?
(just kidding)
Of course, these objections are a bit over the top for such an easy example. I just made them to show you the many surroundings of code. Programming is far more than coding - or you have a big team with specialists for those tasks. If you are interested in a funny read about this subject, I recommend Tom DeMarco: The Deadline. It's worth every penny, but maybe one must have seen real projects before to laugh as hard as I did.

#### fbs7

haha, so 06729 is not the solution for the leading 0, correct? No problem, same algorithm should find another solution starting with a digit. Lemme try it.

#### fbs7

New attempt, same algorithm

Solution is n=15486, 2n=30972
Code:
0123456789 abcde fghik, 1 try a in 123456789, can't start with 0 per fresh_42
0..3456789 1bcde 2ghik, 2 bcde <= 4999, try b in 03
0..3456789 10cde 20hik, 3 rejected repeated 0
0..3456789 13cde 21hik, 3 rejected repeated 1
0.2.456789 1bcde 3ghik, 2 bcde >= 5000, try b in 56789
..2.4.6789 15cde 30hik, 3 cde <= 499 try c in 24
......6789 152de 304ik, 4 de <= 49 rejected no possible values for d
....4.6789 152de 305ik, 4 de >= 50 rejected repeated 5
..2...67.9 154de 308ik, 4 de <= 49 try d in 2
......67.9 1542e 3084k, 5 e <= 4 rejected repeated 4
......67.9 1542e 3085k, 5 e >= 5 rejected repeated 5
..2...678. 154de 309ik, 4 de >= 50 try d in 678
.......78. 1546e 3092k, 5 e <= 4 rejected no possible values for e
..2....78. 1546e 3093k, 5 e >= 5 rejected repeated 3
..2...6.8. 1547e 3094k, 5 e <= 4 rejected repeated 4
..2...6.8. 1547e 3095k, 5 e >= 5 rejected repeated 5
..2....7.. 1548e 3096k, 5 e <= 4 will try e in 2
.......7.. 15482 30964, 5 e <= 4 rejected repeated 4
.......... 15486 30972, stop

#### fresh_42

Mentor
2018 Award
New attempt, same algorithm

Solution is n=15486, 2n=30972
Code:
0123456789 abcde fghik, 1 try a in 123456789, can't start with 0 per fresh_42
0..3456789 1bcde 2ghik, 2 bcde <= 4999, try b in 03
0..3456789 10cde 20hik, 3 rejected repeated 0
0..3456789 13cde 21hik, 3 rejected repeated 1
0.2.456789 1bcde 3ghik, 2 bcde >= 5000, try b in 56789
..2.4.6789 15cde 30hik, 3 cde <= 499 try c in 24
......6789 152de 304ik, 4 de <= 49 rejected no possible values for d
....4.6789 152de 305ik, 4 de >= 50 rejected repeated 5
..2...67.9 154de 308ik, 4 de <= 49 try d in 2
......67.9 1542e 3084k, 5 e <= 4 rejected repeated 4
......67.9 1542e 3085k, 5 e >= 5 rejected repeated 5
..2...678. 154de 309ik, 4 de >= 50 try d in 678
.......78. 1546e 3092k, 5 e <= 4 rejected no possible values for e
..2....78. 1546e 3093k, 5 e >= 5 rejected repeated 3
..2...6.8. 1547e 3094k, 5 e <= 4 rejected repeated 4
..2...6.8. 1547e 3095k, 5 e >= 5 rejected repeated 5
..2....7.. 1548e 3096k, 5 e <= 4 will try e in 2
.......7.. 15482 30964, 5 e <= 4 rejected repeated 4
.......... 15486 30972, stop
Too big. I think your algorithms doesn't consider the carries and rejects possible solutions.

#### fbs7

Ops... big fingers got in the keyboard's way (error in the 4th line of previous post)... now I flunked high-school; trying again.

Btw, I wonder if there's a way to solve this through logic instead of searching for a solution; I tried a few times, but the solution through logic evaded me.

On 3rd try, solution is n=13485 2n=26970; if this is still wrong I'm giving up high school and going back to primary school
Code:
0123456789 abcde fghik, 1 try a in 123456789, can't start with 0 per fresh_42
0..3456789 1bcde 2ghik, 2 bcde <= 4999, try b in 03
...3456789 10cde 20hik, 3 cde <= 499 rejected repeated 0
...3456789 10cde 21hik, 3 cde >= 500 rejected repeated 1
0...45.789 13cde 26hik, 3 cde <= 499 try c in 04 (this is the line that had a bug... 2*13 = 26, not 21, haha)
....45.789 130de 260ik, 3 de <= 499 rejected repeated 0
....45.789 130de 261ik, 3 de >= 500 rejected repeated 1
0....5.7.9 134de 268ik, 3 de <= 499 try d in 0
.....5.7.9 1340e 2680k, 4 e <= 4 rejected repeated 0
.....5.7.9 1340e 2681k, 4 e >= 5 rejected repeated 1
0....5.78. 134de 269ik, 3 de >= 500 try d in 578
.......78. 1345e 2690k, 4 e <= 4 rejected no values for e
0......78. 1345e 2691k, 4 e >= 5 rejected repeated 1
0....5..8. 1347e 2694k, 4 e <= 4 rejected repeated 4
0.......8. 1347e 2695k, 4 e >= 5 try e in 8
0......... 13478 26956, rejected repeated 6
0....5.7.. 1348e 2696k, 4 e <= 4 rejected repeated 6
0....5.... 1348e 2697k, 4 e >= 5 try e in 5
.......... 13485 26970, stop

#### fresh_42

Mentor
2018 Award
On 3rd try, solution is n=13485 2n=26970; if this is still wrong I'm giving up high school and going back to primary school
Code:
0123456789 abcde fghik, 1 try a in 123456789, can't start with 0 per fresh_42
0..3456789 1bcde 2ghik, 2 bcde <= 4999, try b in 03
...3456789 10cde 20hik, 3 cde <= 499 rejected repeated 0
...3456789 10cde 21hik, 3 cde >= 500 rejected repeated 1
0...45.789 13cde 26hik, 3 cde <= 499 try c in 04 (this is the line that had a bug... 2*13 = 26, not 21, haha)
....45.789 130de 260ik, 3 de <= 499 rejected repeated 0
....45.789 130de 261ik, 3 de >= 500 rejected repeated 1
0....5.7.9 134de 268ik, 3 de <= 499 try d in 0
.....5.7.9 1340e 2680k, 4 e <= 4 rejected repeated 0
.....5.7.9 1340e 2681k, 4 e >= 5 rejected repeated 1
0....5.78. 134de 269ik, 3 de >= 500 try d in 578
.......78. 1345e 2690k, 4 e <= 4 rejected no values for e
0......78. 1345e 2691k, 4 e >= 5 rejected repeated 1
0....5..8. 1347e 2694k, 4 e <= 4 rejected repeated 4
0.......8. 1347e 2695k, 4 e >= 5 try e in 8
0......... 13478 26956, rejected repeated 6
0....5.7.. 1348e 2696k, 4 e <= 4 rejected repeated 6
0....5.... 1348e 2697k, 4 e >= 5 try e in 5
.......... 13485 26970, stop
This is correct, keep on learning!

The manual solution isn't really better than your algorithm. It goes along the following lines:
• If the 0 is in n, then 1 and 5 must be in 2n.
• If the 0 is in 2n, then 5 and 1 must be in n.
• If the 9 is in n, 8 and 4 in 2n must be in it.
• If the 9 in 2n is in, 4 and 8 must be in n.
etc.

Last edited:

#### mfb

Mentor
Minimal python implementation:
Code:
for i in range(10000,100000):
if ''.join(sorted(str(i)+str(2*i)))=="0123456789":
print i
break

#### Bosko

Gold Member
3.) Show that $$\int_{0}^{1} dx \int_{x}^{\sqrt{x}} f(x,y)\,dy = \int_{0}^{1} dy \int_{y^2}^{y} f(x,y)\,dx\,.$$
The integration area for f(x,y) function is ... https://www.wolframalpha.com/input/?i=plot+y=sqrt+x,y=x,++x=0,1

1) If we calculate first by x from 0 to 1 and then by y from x to x1/2 we get
$$\int_{0}^{1} dx \int_{x}^{\sqrt{x}} f(x,y)\,dy$$

2) If we calculate first by y from 0 to 1 and then by x from y2 to y we get
$$\int_{0}^{1} dy \int_{y^2}^{y} f(x,y)\,dx\,.$$

1) and 2) are equal because it is the same function f(x,y) on the same area but calculated on two different ways
$$\int_{}^{} \int_{Area}^{} f(x,y)\,dx dy\,.$$
You could do it with the upload button at bottom right of the edit field, but I would appreciate if you wouldn't. Here's a guideline to write formulas on PF:
https://www.physicsforums.com/help/latexhelp/
Thanks

#### Attachments

• 19 KB Views: 142
Last edited:

#### fbs7

Trying 5c

(100000A + 10000B + 1000C + 100D + 10E + F).3 = (100000B + 10000C + 1000D + 100E + 10F + A)
(100000A + 10000B + 1000C + 100D + 10E + F).2 = (100000C + 10000D + 1000E + 100F + 10A + B)
(100000A + 10000B + 1000C + 100D + 10E + F).6 = (100000D + 10000E + 1000F + 100A + 10B + C)
(100000A + 10000B + 1000C + 100D + 10E + F).4 = (100000E + 10000F + 1000A + 100B + 10C + D)
(100000A + 10000B + 1000C + 100D + 10E + F).5 = (100000F + 10000A + 1000B + 100C + 10D + E)

(300000A + 30000B + 3000C + 300D + 30E + 3F) = (100000B + 10000C + 1000D + 100E + 10F + A)
(200000A + 20000B + 2000C + 200D + 20E + 2F) = (100000C + 10000D + 1000E + 100F + 10A + B)
(600000A + 60000B + 6000C + 600D + 60E + 6F) = (100000D + 10000E + 1000F + 100A + 10B + C)
(400000A + 40000B + 4000C + 400D + 40E + 4F) = (100000E + 10000F + 1000A + 100B + 10C + D)
(500000A + 50000B + 5000C + 500D + 50E + 5F) = (100000F + 10000A + 1000B + 100C + 10D + E)

as A,B,C,D,E,F in 0..9, then

3F mod 10 = A
2F mod 10 = B
6F mod 10 = C
4F mod 10 = D
5F mod 10 = E

(30E+3F) mod 100 = (10F + A)
= (30(5F mod 10)+3F) mod 100 = 10F + (3F mod 10)

so can just try all numbers from F=1 to F=9

(30.(5.1 mod 10) + 3.1) mod 100 = (30.5+3) mod 100 = 53 <> 10.1 + (3.1 mod 10) = 13
(30.(5.2 mod 10) + 3.2) mod 100 = (30.0+6) mod 100 = 6 <> 10.2 + (3.2 mod 10) = 26
(30.(5.3 mod 10) + 3.3) mod 100 = (30.5+9) mod 100 = 59 <> 10.3 + (3.3 mod 10) = 39
(30.(5.4 mod 10) + 3.4) mod 100 = (30.0+12) mod 100 = 12 <> 10.4 + (3.4 mod 10) = 42
(30.(5.5 mod 10) + 3.5) mod 100 = (30.5+15) mod 100 = 65 <> 10.5 + (3.5 mod 10) = 55
(30.(5.6 mod 10) + 3.6) mod 100 = (30.0+18) mod 100 = 18 <> 10.6 + (3.6 mod 10) = 68
(30.(5.7 mod 10) + 3.7) mod 100 = (30.5+21) mod 100 = 71 = 10.7 + (3.7 mod 10) = 71
stop

so F=7, therefore
A = 3.7 mod 10 = 1
B = 2.7 mod 10 = 4
C = 6.7 mod 10 = 2
D = 4.7 mod 10 = 8
E = 5.7 mod 10 = 5

142857.1 = 142857
142857.3 = 428571
142857.2 = 285714
142857.6 = 857142
142857.4 = 571428
142857.5 = 714285

What a beautiful problem!!!! I'd never imagine a 6-digit number multiplied like that would just twist around itself. Really amazing! Well done, fresh_42, you really have an impressive mind!!!

I wonder what deep property lies buried in this number, so that it does that, other than it looks suspiciously like 1/7 = 0.142857...

#### fbs7

Hmmm... maybe that comes down to this...? This is super!

1/7 = 0.abcdefabcdefabcdef..
1E6.1/7 = abcdef.abcdefabcdef..
1E6.1/7 - 1/7 = abcdef
(1E6-1)/7 = abcdef = 999999/7 = 142857 => 999999 = 142857 * 7

similarly

1/7-0.1 = 0.0bcdefabcdefabcdef..
1E7.(1/7-7/70) = bcdefa.bcdefabcdef...
1E6.(3/7) = bcdefa.bcdefabcdef...
1E6.(3/7) - (3/7) = bcdefa = (999999)*3/7 = 428571 => 999999 = (428571)*7/3 = 142857 * 7

therefore 428571 = 142857 * 3

I bet the other ones go through the pattern. What a wonderful trick!! The digits on this 1/7 dude must make a group of some kind, I guess!

#### fresh_42

Mentor
2018 Award
I wonder what deep property lies buried in this number, so that it does that, other than it looks suspiciously like 1/7 = 0.142857...
It does not only look like it, it is the reason:
If $\sigma$ notes the cyclic shift by one digit ($\sigma(ABCDEF)=BCDEFA$) we get with $x=ABCDEF$
$$x \cdot 10^k \equiv \sigma^k(x) \operatorname{mod}7$$
i.e. $\sigma$ acts like the multiplication by $10$ in $\mathbb{Z}_7\,,$ $10:7=1.42857 \ldots \,.$

mfb

#### DeathByKugelBlitz

Gold Member
5b could be done in Python?

First calculate 1000! then use python to count the zeroes?

#### fresh_42

Mentor
2018 Award
5b could be done in Python?

First calculate 1000! then use python to count the zeroes?
I guess a simple count is easier and faster.

#### DeathByKugelBlitz

Gold Member
5b:

import math
A = str(math.factorial(1000))
A.count('0')

472

#### fresh_42

Mentor
2018 Award
5b:

import math
A = str(math.factorial(1000))
A.count('0')

472
This is not correct. You cannot count those in between!

#### DeathByKugelBlitz

Gold Member
I got this but i made mistake somewhere
import math
A = (str(math.factorial(1000)))
B = (str(int(math.factorial(1000)))[::-1])
C = len(A) - len(B)
print(C)

"Math Challenge - March 2019"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving