Hello, I have a few math books with fun/neat math problems. Let's do some together. Post your favorite math problems as well:
A problem involving operations on digits
Take an expression of the form (((7^7)^7) ... ) ^7
What is the least significant (rightmost) digit of the resultant evaluation? Why?
I really liked this one: Day 3
You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward.
...
How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port?
TIME COMPLEXITY, RECURSIVE PROCEDURES, RECURRENCE RELATIONS, AND SORTING ALGORITHMS
But if you've been in any CS class where optimization is a thing, you've probably done this before.
Merge Sort, a recursive procedure, works by breaking an unsorted array of numbers down into two evenly sized groups, recursively and until all groups are of size 1, then merges/sorts them back together into a singular ordered array. We will define a function T(n) that signifies the number of comparisons to sort a list of n elements using the procedure. You may assume that n is a power of 2.
In a single operation on a list of size n, we split the list into two sub-groups of even size, which results in a total of 2*T(n/2) comparisons. The final merging also takes n-1 comparisons to bring both sub-groups together into one. The base case takes no comparisons.
Therefore,
T(n) = 2*T(n/2) + n - 1
T(1) = 0
The question is to find a closed form solution to the recurrence relation developed above to get the average running time of the procedure.
I said fun math problems not homework
I finished that class a year ago.
This is excellent! But you don't even have to go that far in pattern recognition. Once you see that 7^7 has a last digit of 3, and 3^7 has a last digit of 7, we know that it's going to alternate back and forth. Since we're going an even number of times, we can see it's going to be 7.
2.) What integers, beginning with 6, become 1/25th of the original integer when the 6 is removed?
This is actually pretty simple when you expand digits considering base 10. The problem is asking for the solution to, in bad notation,
6XYZ = 25 * XYZ
Or in a proper notation
6 * 1000 + (X * 100 + Y * 10 + Z) = 25 * (X * 100 + Y * 10 + Z)
6 * 1000 / (X * 100 + Y * 10 + Z) = 24
X * 100 + Y * 10 + Z = (6/24 * 1000) = 250
Back to the silly notation,
XYZ = 250
then 6250 works for this. You can repeat this for any length of digits >= 3 and find the integers are defined as 625 * 10^n, n >= 0.
You can do the same thing for #1.
1.) What integers, when the least significant digit is removed are divisible by the new integer?
The problem is to solve XYZ | XY (for example, 100 | 10, but 122 ~| 12). Examining the integers carefully, you can decompose the left hand side into the 1s and 10+s columns like so:
XYZ = XY * 10 + Z
Then the question becomes find all XYZ such that XY * 10 + Z | XY. Separating the two left hand terms, we know (XY * 10) | XY is always true (XY always divides into itself), so an integer is sufficient if Z | XY. Z then has to be an integer multiple of XY. Since Z is one digit by definition and XY is two, the only integer you can multiply XY by to get one digit is 0. Then Z = 0, and so finally integers that end in zero that have two or more digits fit the bill.
10n, n != 0
Good call! For two-digit numbers:
XY | X
X * 10 + Y | X
Y | X
Y = nX, n >= 0
Any two-digit number with its ones digit being a multiple of the tens. 90, 99 are also on that list.
Technically so are all the numbers -9 to 9.
Just waiting for someone to post the proof that 1+1 is 2
https://files.facepunch.com/forum/upload/132997/45fab38b-4663-40ac-8b44-1d6489495968/Principia_Mathematica_54-43.png
From Principia Mathematica, Whitehead and Russell.
Side question: I heard that this work was an attempt to define, from the ground up, the rules of mathematics. However, I also heard that Kurt Godel's "Incompleteness Theorem" proved that it was impossible to define all the rules of mathematics consistently. Can anyone who's way smarter than me comment?
The incompleteness theorem says, more or less, that in any logical system powerful enough to express natural numbers, there exist statements that are true but cannot be proven true. I can't really comment on Principia Mathematica because I'm not really familiar with the historical context.
The thing is, while it would be nice to have a system that is able to "prove its own correctness", what we have currently is really not that bad. The standard axiomatic system that's used in mathematics (ZFC) has really only one axiom that's under any dispute: the axiom of choice. And even with that, the ZF theory, without that axiom, is perfectly fine for a lot of proofs. If you take a look at the rest of the axioms, I'm sure you'll agree that they're reasonable "assumptions" that you want to have when thinking about things
In CS, there are a lot of results that depend on NP!=P even though this hasn't been proven. If it turned out that the opposite is true, that would of course invalidate those results. The situation with the axiomatic systems isn't really the same because isn't not like we can prove the axioms wrong. It's just a system in which we decided to do logical reasoning that's most in line with what we (humans) think is logical.
why is 9 afraid of 7?
because 7 is black and 9 was raised by prejudiced parents
Archived Problems
aaa
More logic/electronics than programming, but I think you guys will appreciate this.
You need to implement this circuit:
https://files.facepunch.com/forum/upload/238785/4b8c3dad-7164-4dbb-8d70-082761804b95/image.png
I.e., take 3 1-bit inputs, and present their complements on 3 1-bit outputs. You can use AND, OR and NOT gates. However, your company is trying out a fancy new silicon manufacturing process, and NOT gates are fabulously expensive; however, the cost of any other gates is negligible in comparison. What is the minimum number of NOT gates required to implement this circuit?
Answer: 2!
Bonus question: It might seem like, if you can implement a 3-inverter circuit with 2 NOT gates, there is some kind of induction proof which shows that you can implement any circuit in the universe with only 2 NOT gates. This is not true. How is the above circuit different from 3 separate NOT gates?
Sorry, you need to Log In to post a reply to this thread.
