The Art of Problem Solving in Wolfram Language '23

Welcome everyone. Thanks for joining this talk. This is a serious talk I've been preparing and given for a couple of years. Right now it's about art of problem solving with Wolfram Language today. This year is 23rd and actually I did another 23rd version for the Warframe Live R D channel before. So yes, I just want to briefly introduce myself. I am Shenhui Yang. I work for Wolfram Alpha team. I had a degree in engineering but I always, always keep a keen eye on mathematics. I like learning some theories but but I think it's quite important is to learn by solving actual problems. And I feel like Wolfram Language is a very powerful tool and the platform to collect and solve interesting problems for mathematics with lots of interesting visualization and analytical tools. So before we start, I would like to just appreciate the team to integrate the ChatGPT feature into Wolfram language. Since version 13 it's getting better and better and I think it helps me a lot. For example, I don't really need to work too much on writing abstract for my talk so it can be answered. The abstract is just two questions. What's the benefit of solving challenging math problems? And it's a Wolfram language are very helpful to tackle this kind of puzzles and you can ask ChatGPT to give it certain Personas and to use this syntax to persistently talk to and chat with the ChatGPT. So well, there is like 300 character limit for abstract but if you ask GPT it will give you a lot of information about why it's benefit to solve challenging math problem and how. Wolfram language is very helpful here. So it shows you some of the context that yes, Wolfram languages can be helpful tool for solving challenging math problems. Sometimes it'll give you different answers, but in general it shows what's the benefit of using this tool to solve problems. Typically, I think the biggest advantage is this platform integrates a lot of different branches of mathematics and even beyond the mathematics like physics and chemistry, astrophysics and so on. So it will give you very comprehensive and all around the tool to help you not only solve this problem, but understand what's behind this problem. And you can scroll down to see a lot of the things that ChatGPT has us on how to use this language to help you solve the problems. It tends to write a lot about it, but in summary it's strong data capabilities, visualization tools and the natural language processing. It's Wolfram Alpha and plus LL. Right now I think it's a very interesting way to extend beyond this notebook for just solving math problems. Of course to use this entire feature you need a subscription key API key from OpenAI, but you don't need the key to view the results. So far I have. But if you want to generate this result, you need API key to work with that. Okay. And then let's move to some of the collections I have contributed so far to the community. These are all problem solving talks on either Live R and D and WTC for the past years. Everything comes with a YouTube link. You can just click that and the notebook is already uploaded to the handout session. So you can just download it and click these files to view the YouTube links. Warframe has already uploaded to the official channel. And also there are some selected community articles. Very interesting, you can read about it. Some of the major topics I have highlighted with Warframe Alpha the search engine logo. So you can just click that and it should show you what's the definition behind the topics. These links are also added to the hyperlinks here so you can click and read those interesting Wolfram community articles about how to use Wolfram language to solve interesting problems. And some of them are actually related to more advanced topics like this Markov chain, which is also related to a recent Numberphile video about Ladder and the Snake game from India. So it's also using the same idea behind it. So you can just watch some of the videos and read our community articles to learn more about the more detailed techniques and knowledges you need to learn about the Wolfram language and the mathematics to tackle these puzzles. Also, I want to quickly mention my future plan for the future talks because most of the problems I demonstrated here want to demonstrate the product and also want to attract more audience. So most of them will be confined to high school levels. But since more and more functionality in the linear algebra and finite field functions are added to Wolfram language and they are getting more matured, I think I can just demonstrate lots of interesting materials in the high level math and with a minimum amount of code. For example, there's a very commonly used finite field application in cryptography. It's called the Mobius transformation. And this is the web page that Dr. Cook has created. And also I have a demonstration that show you how to recreate this diagram just with the latest finite field feature in Mathematica. And you can also ask ChatGPT here. Why would I focus on these new technologies here because they are used quite often in the cryptography. I think this branch of math was kind of not kind of minor, but it's get really popular after blockchain and cryptography are kind of popular recent years. So it's highly correlated to the hottest topic in finance technology. So I think it's also the feature is just written added to Wolf language. I think it's a good time to show you some interesting examples with that. This one will be covered in today's topic because I have office hour after this talk we will move some of the more detailed topics into the office hour starting from 3:00'. Clock. So I will just go through some of the interesting problems I have curated so far and if you have more questions, I'm trying to answer you in very detail in the office hour. Okay, so this is the end of the intro and let's dive into the problems. Okay, the first problem are from the first problem. Let me just go back here. There's a kind of outline of the problems here. The six challenging problems they are going to cover number theory, one game, Euclidean geometry and combinatorics. Not everything in one problem, but the six problem will fall into these categories and features strong visualization techniques. One of them using the function compile to accelerate the computation. And we are focused on the symbolic computation as well. As I mentioned, some of the discussion will move to office hour for the details. The first problem I'm going to demonstrate is from the book I mentioned in the introduction. It's from Erdos to Kyiv. Erdos was a very famous Hungarian mathematician and that's Kyiv also means some of the Soviet Union level Math Olympiad stuff. So it was a very classic book to demonstrate to collect interesting problem and demonstrate a very strong problem solving skills. Okay, the first problem is quite interesting. Its title is Ed Doolittle's solution on this guy. Under the flow function of k times square root two equal to perfect power over two, for instance, you put PI inside this flow function. It just return 3 because it truncates all the integer part and remove the fraction part for you. So for positive number it's really straightforward. There's slightly more trivial, more nuance around the negative numbers, but we are not going to cover them today. But the problem is very straightforward. It gives you some simple background because we know square root 2 is irrational. So the value k times square root 2 is never integer. For all the positive integer K, you know, for example, if it's rational, it's sort of a fraction. So if 5 over 3 times 6 you always get integer. But because square root 2 is never a fraction, so we regardless of k true choice of K, you will never get integer. So in this problem we're concerned with the sequence generated by the integer part of the K times square root two. Okay, so it's something that we want to find the integer that K times square root two and two times square root two, three times square two and so on. To take the integer part. And the thing is we, we don't want all the integers, we want only certain type of integers. So one is this type of integer must be a prime tower of a tower, a prime tower or a power of prime. In 42, for example, all the highlight number is 2 to the power of something. It's something is an integer. For example 2 to power 0, 2 to power of 1, 2 to the power of 2, 2 to the power 3 and 2 to the power of 4 and 2 to the power of 5. So it's 5 two times together. So these are the interesting part where we are looking at and the questions ask whether we have infinity such thing, you know, infinity such thing. And the key is also to understand that this infinite part of thing is not all part of thing. For example, if you go, you see this 0, 1, 2, 3, 4, 5 and. But we. The 64 is not here. So for infinity part we can miss something. It can be a subset, e.g. all the even numbers, we basically it's infinite set. But we miss all the other members here. Okay, so that's the question whether we can have infinite of such things here. And also there's another book I mentioned in the brief introduction in the some in the abstract on the website is. It's called the Miniature. It's written by a very famous mathematician, Titu Andreescu. He is now I think as the head of maa. And also he used to be the coach for the US IMO team for a long time. And in this book he asked a question whether the last digit of a floor square root of K to the power of K in decimal is periodic or not for odd integer K. So this is. These two problems are strongly related. And what we can do here is before we dive into the analysis, we can just plot some of the results with this with Wolfram language. So for example, I just put for this problem I just plot floor of square root of k to the power K and mod 10 because I'm interested in the last digit and k takes from 1 to 10,000 because 10,000 is 100 times 100. So I just partition to 100 block so I can plot in the perfect square and give you some color function here. So it looks like there is no rule in the picture and Comparing to that, there's also a no rule inside for this flow function. And that's exactly what we want. Because square root two is irrational. There is really no obvious pattern in the decimal places. And that's something we want to look. Because if we do have something periodic, that would be really troublesome for number theorist. And some of the functions I use here is real digits. And this one tells you that function the 503 in decimal form starting with 1 and have a repeating 6. And if you flip that thing, because 6 is. If you look at this, 6 is sort of in the third level of the list here. But this guy is only at the second list. So that means it start with 6 and no repeating stuff. So that's the real digits for you. But for square root two it shows nothing, it does nothing to you. Because there is no repeating pattern, no obvious pattern for all the irrational numbers. So this one should return evaluated. But I can do that with specifying the number of digits that I want to truncate. So that gives you the truncated digits for 10 digits for that. And the last one means the first one is like times 10. So there is one digit to the left side of the decimal point. So that's the real digits function. And you can also just convert square root two into floating number form. It will give you some of the decimal points. The key takeaway to solve this problem. Actually these two problems using the exact same idea to solve is to understand that because we looking for like a two to the power over n here. So what should we do to this part? Because you know, square root two really is messy in the decimal point. What can we do to that? The idea is behind this really powerful real digits functions. You can specify the base function for this number. For example, this is 1/2, 1/2 in decimal 2. And let's take 10 decimal places is just a 0.1. So there's no point, no number to the left of decimal point. So this is a same number we can view in different basis. And because we are looking for two to the power of nature. So it's nature for us to think of this problem in binary digits. So this is basically the idea, the first key idea to use this function to demonstrate square root two in terms of binary digits. And also there are some introduction. This shows you how the flow function works with this square root two. Because it's just a trunk removed all the decimal parts. And to show that I have more than a lot more candidates to have to be like two to the power of something. I Can just increase the number of the T. T is like T Times Square Root 2. Here it shows you more candidates. But this problem with this code is it's getting really slow when the number gets really large. And by the way, I just want to quickly mention here, this is a very common technique or trick to test if a number is a binary digit. You do a bit end, so it's like bitwise end between this number and this number minus one. If to return zero, it means this integration is a perfect power of two, otherwise it's not. So if it is true, highlight this number. If it's not, just get rid of it. So if you try this thing I did, it's like it takes about like four seconds to evaluate. So it really takes some time to do that. I'm not going to show that. But to test more numbers here I used a function compile from the I think version version 13 and I think it's getting better in the later version. So this is a machine code level things to compute these to find this 2 to the power N. So I did this one. This is like 2.5 million numbers. It should take about 4.8 seconds to complete that. But this one comes with 2 billion numbers and it should be ending within like 2 seconds. So it does 2 billion iterations. So it's really really fast. It's native C code speed. So it tests all these numbers and give you the valid candidates. And if you try that, try all the numbers and let's take the log two of them, it shows they are all perfect powers, 01 and 31. Okay, so it speed up is around 2100 is like 2000 times faster than the interpreted version. So if you really want to do something brute force wise, this is the good way to go. Then let's come to the analysis. Why there is an infinite number of candidates that works the first we want to show that there's no patterns. And the essential condition for no pattern is you must have infinite ones in BAS2 for square brute 2. So otherwise if they are finite number of ones then eventually you have something like all the zeros to the to the right hand side. So all the zeros means all zero means it's a rational, so it's a contradiction. So we must have infinite number of ones in base two. And this basic diagram shows it's. It's kind of messy. If there like only finite number of zeros you will see all the light blues truncated at some after some digits. And the, the key idea to solve this problem is you need to find this, this condition. Because two to the power of time, this thing has infinite number of ones square root has infinite number ones in the. In the decimal place in the binary. In the binary base. So 2 to the time of K times square root 2 is basically do a bit shift left for all the digits. So you have everything that's 0.10. You always have some of the. You will encounter one. And recall that 1/2 in the binary display is just 0.1. So you will have as long as you shift something with one to the right hand side of a decimal, it must be larger than 1/2. And then 1/2 is larger than this guy. And this is the key. We basically find a sufficient condition to generate this inequality. And you do a little bit of algebra for the highlight side and highlight side and you will get this one. And this is the fraction part for the final solution. So that one we can take a look at it is this is true and false. And we can plot that. We skip that. But eventually you will have. Eventually you will see is there infinite number of ones and zeros in the list. And then you do this algebra. It's basically using the flow function property that it's immune to addition of integer part. So that's the algebra you do. And eventually you will come close come to this guy. So there is infinite amount of number k such that. Such that this inequality holds. And these are the validated K for this value. And then we find all the valid case here limited to 200. And you can, you can go more. Yeah, like 500, 600 and go more. Just we just truncate at 200. And this will allow us to generate very large numbers. For example, this, these are all this K. This is the integer n Times Square Root 2. And take the floor function of that, it would give you two to the power over N. And if you don't believe that you can just test all the other values. We can do this bit end. So if It's A by 2 to the power N minus itself, it should be 0. Everything is a perfect square and also a perfect perfect power of two. Or we can do that. So these are the powers. So from 2 to the power of 2 and 2 to the power of 199. So in this case, so you can go more and more, but you have to increase the precision here because if you need just more decimal place to handle a much higher power of two to the power or something. Okay. And this also shows you why the problem I mentioned in miniature works so this one, if you take this plot, it's 400, it's the same thing, but it's the same result. But we convert to binary digit. You look at that, there's really no pattern in the result. So here is a quick comment. If the last digit in the floor 2 to the power k times square root 2 is periodic, it must be periodic in binary form. And if it's binary form, it's periodic. This simply means if it's a periodic in binary form. So with this function, we simply just extract all the binary digits one by one. And of course, if you look at this image, it's really, really not periodic. So we use the same argument as the function before. Okay, so this is the first problem. It's quite interesting, it's quite a challenging one. And you may want to read those handouts and we can discuss it in detail during the office hour. Okay, And I want to also show quickly a this is the first one I was talking about. This is the first, the Mobius transformation of a finite field. It's about a new feature in Mathematica, for example. This is the sample page I mentioned in the beginning. So if you take a look at this result. And he also offered some Python code here, but we can do a more consistent code to generate the entire thing. This is used in cryptography. It's used finite field to generate a random permutation. So if you look at these two graphs, the left one is generated within the latest version of Wolfram language and the right one is from the webpage. They should look exactly the same. If you look at the trapezoid here, there is a bigger trapezoid here. It's the same. It's exactly same. And we have two points that comes with these lines because they are self loops, the self loops, I have just removed them for a clear visualization for the graph. So the we use the same idea to generate that, but in Wolfram language, right now you can do that more consistently. So this graph comes with 18 dots, but it's generated on finite field 17. So there are only 17 numbers in 17 elements in its final field because it's not a compact for our Mobius transformation, that Mobius Mobius transformation is just AZ +B over CZ +D and the FZ is replaced with a finite element field. So this thing is usually comes if you do the computation, you'll find obviously there's no rule in this kind of permutation, and that's why it's good for cryptography. And this one is First I convert the number Z. Usually you can put a complex number here into finite field, finite field element. It you just put a number and wrap around finite field element or finite field. This thing you can put like two here. Okay, so once you have that, everything is labeled in the ordinary nature number sequence. But the issue with that, but the issue with that is you don't have all the elements available because if you look at the cz plus d, that's the denominator. And sometimes you will have zero. And this is where you have zero here. So 2 is really not something you can easily handle this time. So this guy need to be handled with care. So there's a terminology in the Riemann manifold and all kind of group theory stuff. It's called a one point compactification because like real number line you don't have holes, but this time you have hole. So in this case you need to patch a hole with the infinity here. So you need to patch infinity and the pre image of infinity here. So that's for example two is the pre image of infinity. And what's the image of infinity is you put infinity inside in the place of a finite element here and it should return FA times fz. It's just think about it, you know, you have like A z plus B and CZ plus D. And as Z goes to infinity, B and D does not matter anymore. So you just have A over C. But we need to do that over finite field. So this is the finite field multiplication here. So you let's do FFA over FFC as FF is you define this way. And then you do have this rule. And everything underneath is the elements operated by the Mobius transform. It's empty here, the Mobius transform. And you have sort of a corresponding one to one relationship. And this is called sort of permutation permutive in place. Permutation is basically everything maps to something else. But these two sets should be identical. So a terminology would be automorphism. It's a map to itself. It's rearrangement of itself. So now you, it's clear that why you have 18 numbers, because it's from 0 to 16, that's 17 items plus infinity, that's 18, so that's the 18th item. So it's 17 plus 1, it's 18. Now let's just program the permutation is I just put all the index for this number because mathematics start with 1. So 1, 2, 3, 4, 5, 6 into 18. It's not 0 to 17. And then you will need to remove two fixed point because for visualization you don't have to remove the point but you remove the self loops so you can see that clearly that there are to a fixed point. So 1 map to 110 map to 10 here and then use a function that I find online to remove the self loops and then I think you just need to specify the layouts and then using the vertex coordinates to specify the how these elements point to its actual coordinates on a circle. Okay so this will generate this diagram for you. You can just click evaluate a notebook. It should just show you all the result that's generated for that. So that's how you use group theory stuff to handle the problems. Okay I think it's time up for this session and I'm going to move to all There are three other interesting Euclidean problem number theory problem and group theory problem into the office hour so keep in touch. I will see you in 30 minutes. Bye bye.