Challenge Math Challenge - March 2019

[mfb]

Minimal python implementation:

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

 

[Bosko]

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\,.$$

Spoiler

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 x^1/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 y² 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

 

[fbs7]

Trying 5c

Spoiler

(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!

Spoiler

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]

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 \,.$

 

[DeathByKugelBlitz]

5b could be done in Python?

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

 

[fresh_42]

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]

5b:

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

472

 

[fresh_42]

5b:

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

472

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

 

[DeathByKugelBlitz]

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)

 

[fresh_42]

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)

It can be done in one line without coding, two, if an explanation line is added!

 

[DeathByKugelBlitz]

It can be done in one line without coding, two, if an explanation line is added!

I'm new to this, only know what we learned in lecture

 

[fresh_42]

I'm new to this, only know what we learned in lecture

You know that every integer can be written as a product of primes? That's all you need, and some 3rd grader divisions.

 

[Ibix]

I'm new to this, only know what we learned in lecture

Your approach should work in principle. Expand your calculation of B over several steps and make sure each one is doing what you think it is - I can think of a couple of likely failure points.

As fresh says, there are more elegant solutions.

 

[DeathByKugelBlitz]

import math
def reverse_int(n):
return int(str(n)[::-1])
A = (math.factorial(1000))
B = (reverse_int(A))
C = int(B)
D = A.count(0)
E = C.count(0)
print(D - E)

NameError: name 'D' is not defined

 

[fbs7]

I tried the 1000! problem with logic, by counting the x10 and x100 numbers, then counting the x2 . x5 combinations that produce 1, 2, 3 and 4 zeroes... but I got the wrong total of zeroes compared to the real number from Wolfram-Alpha's ...

That puts me back in kindergarten, oh no.. :(

 

[fresh_42]

I tried the 1000! problem with logic, by counting the x10 and x100 numbers, then counting the x2 . x5 combinations that produce 1, 2, 3 and 4 zeroes... but I got the wrong total of zeroes compared to the real number from Wolfram-Alpha's ...

That puts me back in kindergarten, oh no.. :(

Why did you count the twos? Were you afraid there might not be enough of them?

 

[fbs7]

Because 2.5 = 10, so each group of 1.2.3.4.5.6.7.8.9 = 2.5.(1.3.4.6.7.8.9) = 10.(36,288)

So numbers that end in 1,3,4,6,7,8,9 don't add any zeroes to the result ( ex x3.x6 = (10x+3).(10x+6) = 100x^2 + 10.(3+6).x + 6.3... no zeroes in any x6.x3 for all x in {0..99} ).

As any number ending in 2 will be followed by a number ending in 5 in the sequence {1..1000}, then for x in 0..99 we have x2.x5 = 100x^2 + 10.(2+5)x + 10 = 100x^2+10(7x+1), therefore x2.x5 add zeroes. So we get 1x3 zeroes from 1000, 9x2=18 zeroes from 100, 200, .. , 900, 90x1 zeroes from 10, 20, ..., 90, 110, 120, ..., 190, 210, ... , 290, .. , 990, = 111 zeroes, plus the zeroes from the multiplications of x2.x5.

The zeroes for x2.x5 will be 1 for each x in 0..99... which is 100 numbers (ex 22.25 = 550); then 1 more for each (10.x^2 mod 10 + 7x+1) that is multiple of 10; then 1 more for each (x^2 mod 10 + 7x+1 ) that is multiple of 100. Inspection shows that only x=7, 17, 27, ..., 97 produces that expression as multiple of 10 (ex 372.375 = 139,500), and only 87 produces an expression that is multiple of 100 (872.875 = 736,000). So the x2.x5 terms produce 100 + 10 + 1 = 111 zeroes.

This calculation yields 222 zeroes, but Wolfram-Alpha shows 249 zeroes, so my result is wrong... I'm missing something and I have no clue what... :-(

Back to kindergarten, fbs7!

 

[fresh_42]

Because 2.5 = 10, so each group of 1.2.3.4.5.6.7.8.9 = 2.5.(1.3.4.6.7.8.9) = 10.(36,288)

So numbers that end in 1,3,4,6,7,8,9 don't add any zeroes to the result ( ex x3.x6 = (10x+3).(10x+6) = 100x^2 + 10.(3+6).x + 6.3... no zeroes in any x6.x3 for all x in {0..99} ).

As any number ending in 2 will be followed by a number ending in 5 in the sequence {1..1000}, then for x in 0..99 we have x2.x5 = 100x^2 + 10.(2+5)x + 10 = 100x^2+10(7x+1), therefore x2.x5 add zeroes. So we get 1x3 zeroes from 1000, 9x2=18 zeroes from 100, 200, .. , 900, 90x1 zeroes from 10, 20, ..., 90, 110, 120, ..., 190, 210, ... , 290, .. , 990, = 111 zeroes, plus the zeroes from the multiplications of x2.x5.

The zeroes for x2.x5 will be 1 for each x in 0..99... which is 100 numbers (ex 22.25 = 550); then 1 more for each (10.x^2 mod 10 + 7x+1) that is multiple of 10; then 1 more for each (x^2 mod 10 + 7x+1 ) that is multiple of 100. Inspection shows that only x=7, 17, 27, ..., 97 produces that expression as multiple of 10 (ex 372.375 = 139,500), and only 87 produces an expression that is multiple of 100 (872.875 = 736,000). So the x2.x5 terms produce 100 + 10 + 1 = 111 zeroes.

This calculation yields 222 zeroes, but Wolfram-Alpha shows 249 zeroes, so my result is wrong... I'm missing something and I have no clue what... :-(

Back to kindergarten, fbs7!

I have serious trouble decoding that! I assume that "xN." doesn't mean the hexadecimal number N?
You shouldn't worry about the last digits, just write $1000!$ as a product of primes.

 

[DeathByKugelBlitz]

import math
def primeFactors(n):
while n % 2 == 0:
print 2,
n = n / 2
for i in range(3,int(math.sqrt(n))+1,2):
while n % i== 0:
print i,
n = n / i
if n > 2:
print n
(primeFactors(math.factorial(1000)))

2 2 13 107 36791

 

[fresh_42]

import math
def primeFactors(n):
while n % 2 == 0:
print 2,
n = n / 2
for i in range(3,int(math.sqrt(n))+1,2):
while n % i== 0:
print i,
n = n / i
if n > 2:
print n
(primeFactors(math.factorial(1000)))

2 2 13 107 36791

Not sure what the string means, as there are plenty of primes in $1000!$. Each prime below $1000$ occurs at least once, and the smaller primes do occur quite often. Fortunately, we are only interested in two primes.

 

[DeathByKugelBlitz]

Not sure what the string means, as there are plenty of primes in $1000!$. Each prime below $1000$ occurs at least once, and the smaller primes do occur quite often. Fortunately, we are only interested in two primes.

This is annoying lol

I'm just going to import math and math.factorial(1000) then count the zeroes myself lol

 

[fresh_42]

This is annoying lol

I'm just going to import math and math.factorial(1000) then count the zeroes myself lol

Count the fives, that'll do.

 

[Ibix]

Not sure what the string means,

Almost certainly, it means that something in the primeFactors function does not respect unlimited precision integers. Not sure which step without a python interpreter to hand.

 

[fbs7]

I have serious trouble decoding that! I assume that "xN." doesn't mean the hexadecimal number N?
You shouldn't worry about the last digits, just write $1000!$ as a product of primes.

Oh, sorry, that was short-hand; that meant x2 = a number ending in 2, that is x2 = (10x + 2), like, x2 = 22 or 42 or 132 and so forth; meanwhile x5 is a the same first digits, but ending in 5, like 25, 45 or 135.

 

[fbs7]

Hmm.. product of primes... what this means... hmm...

 

[fbs7]

Oh... I see!... what a smart man! This is my attempt at 5b:

Spoiler

17! has 17 numbers in it. So, between 1 and 17 there are floor(17/2)=8 numbers divisible by 2! They are 2,4,6,8,10,12,14,16. Then there are floor(17/2^2)=4 numbers divisible by 4! They are 4,8,12,16. And floor(17/2^3)=2 numbers divisible by 8, and floor(17/2^4)=1 numbers divisible by 16.

Therefore 17! must be 2^(8+4+2+1)*x = 2^15*x = 32768*x; proof is

X = 17! = 355687428096000 = 32768*10854718875

What an excellent thing! So

X = 1000! = 2^a * 3^b * 5^c * etc...

Now, there are more numbers (<X) divisible by 2 than there are numbers divisible by 5, therefore a>b, therefore each factor 5 can be paired with a factor 2 to generate a number 10, and as no other pair of primes multiply to 10 or multiple, then no other primes matter other than 5!

So, we only need to consider the number of factors for 5 (not the number of twos! now I get it - haha!)

X=1000!
5^1... floor(1000/5)=200
5^2... floor(1000/25)=40
5^3... floor(1000/125)=8
5^4... floor(1000/625)=1
5^5... floor(1000/3125)=0
stop

The number of 2*5=10 factors in the factorization by primes is therefore 200+40+8+1=249! And that matches Wolfram-Alpha! Hooray!

This is extraordinary! If I could cook, I'd cook you some cookies, fresh_42!

 

[fresh_42]

The number of 2*5=10 factors in the factorization by primes is therefore 200+40+8+1=249! And that matches Wolfram-Alpha! Hooray!

And without code it is a two liner:

We have enough $2$ for pairing with $5$, so we only need to count the number of prime factors $5$ in $1000!$ which is

$\lfloor(1000/5) \rfloor + \lfloor(1000/25)\rfloor + \lfloor(1000/125)\rfloor + \lfloor(1000/625)\rfloor=200+40+8+1=249$

 

[fbs7]

Now I see the error in my original thought process. The right solution counts:

1 zero for each multiple of 5 (all of them end in 5 or 0)
+1 zero for each multiple of 25 (all of them end in 25, 50, 75 or 00)
+1 zero for each multiple of 125 (all of them end in 125,250,375,500,625,750,875 or 000)
+1 zero for each multiple of 625 (for <1000, that means end in 625)
----------------
249 zeroes

My original count that yielded 222 zeroes went from the last digits:

1 zero for each number ending in 0
+1 zero for each number ending in 00
+1 zero for each number ending in 000
+1 zero for each number ending in 5
+1 zero for each number ending in 75
+1 zero for each number ending in 875
---------------
222 zeroes

Problem with the 2nd count is that misses zeroes on numbers that end in 25,50,125,250,375,625,750. The right count on the 2nd method should have been:

1 zero for each number ending in 0
+1 zero for each number ending in 00
+1 zero for each number ending in 000
+1 zero for each number ending in 5
+1 zero for each number ending in 25, 50 or 75
+1 zero for each number ending in 125, 250, 375, 500, 625, 750 and 875
+1 zero for each number ending in 625
---------------
249 zeroes

The underlying logic fail is that I failed to consider what happens to (10x+2)*(10x+5) when x itself is a multiple of 5. Of course the 1st method is much simpler.

This kind of thing is a common problem, I suspect: one goes down instinctively in some direction, and ends in a rabbit hole that he can't get out of. Mind was decided in considering in detail the last digits of the numbers, but didn't get it right and was blind to an easier approach.

 

[mfb]

By the way: Python can calculate the factorial correctly.
math.factorial(1000) -> long number
len("[copied zeros]") -> 249

Python also has "rstrip", which makes it a one-liner:

>>> len(str(math.factorial(1000)))-len(str(math.factorial(1000)).rstrip("0"))
249

But the insight that it is sufficient to count factors of 5 is much better.