Challenge Math Challenge - March 2019

  • Thread starter fresh_42
  • Start date
  • Featured

fresh_42

Mentor
Insights Author
2018 Award
9,490
6,502

Bosko

Gold Member
15
3
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

Science Advisor
Insights Author
Gold Member
821
419
321
32
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
Insights Author
2018 Award
9,490
6,502
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.

  • Should you have asked?
    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.
 
321
32
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.
 
321
32
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
Insights Author
2018 Award
9,490
6,502
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.
Your first solution was close!
 
321
32
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
Insights Author
2018 Award
9,490
6,502
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! :smile:

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:
32,372
8,350
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
15
3
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

Screenshot 2019-03-07 at 16.08.43.png

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

Last edited:
321
32
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...
 
321
32
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
Insights Author
2018 Award
9,490
6,502
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 \,.##
 
  • Like
Reactions: mfb

DeathByKugelBlitz

Gold Member
22
11
5b could be done in Python?

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

DeathByKugelBlitz

Gold Member
22
11
5b:

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

472
 

DeathByKugelBlitz

Gold Member
22
11
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)
 

Want to reply to this thread?

"Math Challenge - March 2019" You must log in or register to reply here.

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

Top Threads

Top