A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
Programming Language:
LISP
Solution:
(defun gen-pytha-triplets ()
(loop named loop-1 for a from 1 to 1000
do (loop for b from 1 to 1000
do (loop for c from 1 to 1000
do (if (and (and (< a b c) (= (+ (* a a) (* b b)) (* c c))) (= (+ a b c) 1000))
(return-from loop-1 (* a b c)))))))
Overview:
Coming soon…
Programming Language:
x86 Assembly
Solution:
; Takes input (n) and prints all triples (a, b, c) such that a^2 + b^2 = c^2 less than n.
format PE console
entry start
include 'win32a.inc'
; ============================================
section '.text' code readable executable
start: ; the program begins here:
call read_hex
mov ebx, eax
loop_1:
dec ebx
mov ecx, ebx
cmp ebx, 0 ; check if we've reached end of outermost loop
; or if input was zero (0).
jnz loop_2 ; if not zero, start first inner loop
jmp exit ; if so, exit
loop_2:
dec ecx
mov edi, ecx
cmp ecx, 0
jnz loop_3
jmp loop_1
loop_3:
dec edi
cmp edi, 0 ; check if we've reached end of inner loop
jnz square_nums ; if not, print number and decrease by 1
jmp loop_2
square_nums:
mov esi, 0 ; initialize esi (our a^2 + b^2)
; part of equation to zero.
mov eax, edi ; square least num (loop 3 num), or a.
mul edi
add esi, eax ; add result (a^2) to esi.
mov eax, ecx ; square second least num (loop 2 num), or b.
mul ecx
add esi, eax ; add result (b^2) to esi.
; esi now contains (a^2 + b^2).
mov eax, ebx ; square largest num (loop 1 num), or c.
mul ebx
cmp esi, eax ; check is (a^2 + b^2), or esi, equals (c^2) or eax.
jnz loop_3 ; if not, continue to next group of numbers.
; otherwise, print numbers.
print_num:
mov eax, ebx
call print_eax
mov eax, ecx
call print_eax
mov eax, edi
call print_eax
jmp loop_3 ; and continue to test next set of numbers.
exit: ; exit the process:
push 0
call [ExitProcess]
include 'training.inc'
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
Programming Language:
LISP
Solution:
(defparameter numlist (map 'list #'digit-char-p (prin1-to-string 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450)))
(defun 13thproduct (numlist)
(defparameter lprod ())
(loop while numlist
do (defparameter p 1)
(loop for x in numlist for y from 1 to 13
do (setq p (* p x)))
(push p lprod)
(setq numlist (cdr numlist)))
(apply 'max lprod))
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10,001st prime number?
Programming Language:
LISP
Solution:
(defun isprime-p(n)
(defparameter isprime NIL)
(if (and (oddp n) (> n 2))
(loop for x from 2 below n
do (if (eql 0 (mod n x))
(progn (setq isprime NIL)
(return NIL))
(setq isprime T))))
(if (eq n 2)
(setq isprime T))
(print isprime))
(defun nth-prime(num)
(defparameter primes NIL)
(defparameter p 2)
(loop while (< (list-length primes) num)
do (if (eql T (isprime-p p))
(push p primes))
(setq p (+ 1 p)))
(print (car primes)))
Overview:
Coming soon…
Programming Language:
x86 Assembly
Solution:
; receives input (n), prints all primes greater than 1 up to n.
format PE console
entry start
include 'win32a.inc'
; ============================================
section '.text' code readable executable
start: ; the program begins here:
call read_hex
mov ebx, eax ; setup counter in ebx
prime_loop:
cmp ebx, 1 ; check that counter is
jbe exit ; below or equal to 1. if so, exit.
; otherwise, continue.
mov eax, ebx ; move counter's value into eax
; (input of 'start_check_prime' loop.
start_check_prime:
mov esi, eax ; store input in esi for later.
cmp eax, 2 ; if input is 2 (special case prime)
je prime ; num is prime. jump to 'prime' label.
cmp eax, 3 ; if input is 3
je prime ; also jump to 'prime' label.
mov edx, 0 ; initialize edx to 0 for div with 32-bit integers [EDX:EAX].
mov ecx, 2 ; setup divsor (2)
div ecx ; check if input is even and
; get half its value for prime check.
cmp edx, 0 ; if edx is 0, remainder of 'div 2' = 0
je n_prime ; input is even.
; Otherwise input is odd. Check for prime.
mov ecx, eax ; setup ecx (counter) with half of input
; and check divisbility by nums up to ecx.
check_prime: ; check for prime loop
mov eax, esi ; restore eax with original input for check_prime.
mov edx, 0 ; initialize edx to 0 for div with 32-bit integers [EDX:EAX].
div ecx ; divide by current ecx (counter) value
cmp edx, 0 ; if input num is evenly divisible by ecx (counter)
je n_prime ; then not prime.
dec ecx ; decrease counter by 1
cmp ecx, 1 ; but make sure counter is above 1 (because all nums evenly
ja check_prime ; divisible by 1). if counter is above 1, check next ecx num.
; once all ecx nums are checked, and no jumps have been made
; from 'check_prime' loop, then number is prime.
; continue to following line.
prime: ; number is prime.
mov eax, esi
call print_eax
dec ebx
jmp prime_loop
n_prime: ; number is not prime.
dec ebx
jmp prime_loop
exit: ; exit the process:
push 0
call [ExitProcess]
include 'training.inc'
The sum of the squares of the first ten natural numbers is,
12 + 22 + … 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is
3025 – 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Programming Language:
LISP
Solution:
(defun sqr(x)
(* x x))
(defun sum-sqr-diff(lim)
(- (sqr (apply #'+ (loop for x from 1 to lim collect x)))
(apply #'+ (mapcar #'sqr (loop for x from 1 to lim collect x)))))
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Programming Language:
LISP
Solution:
(defun smul (lim)
(defparameter nlim (apply '* (getprimes lim)))
(defparameter num nlim)
(loop while (/= 0 (apply '+ (mapcar (lambda (x) (mod num x))
'(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))))
do (setf num (+ num nlim))
(format t "num is ~a~%: " num)))
(defun isprime-p(n)
(defparameter isprime NIL)
(if (and (oddp n) (> n 2))
(loop for x from 2 below n
do (if (eql 0 (mod n x))
(progn (setq isprime NIL)
(return NIL))
(setq isprime T))))
(if (eq n 2)
(setq isprime T))
(print isprime))
(defun getprimes(lim)
(defparameter primes NIL)
(loop for x from 1 to lim
do (if (eql T (isprime-p x))
(push x primes)))
(print primes))
Overview:
This solution first generates all primes from 1 – “lim” or 20 in this example. Once primes are generated, they are multiplied together and the product is used to generate multiples of that number. These multiples are then tested in smul().
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Programming Language:
LISP
Solution:
(defun 3pal()
(defparameter l3pal 0)
(loop for x downfrom 999 to 111
do (loop for y downfrom 999 to 111
do (if (equal (write-to-string (* x y)) (reverse (write-to-string (* x y))))
(if (> (* x y) l3pal)
(setq l3pal (* x y))))))
(format t "~a ~%" l3pal))
What is the largest prime factor of the number 600851475143 ?
Programming Language:
LISP
Solution:
(defun lprimefactor(num)
(loop for x in (reverse (getprimes 10000))
do (if (eql 0 (mod num x))
(format t "~a is a prime factor of ~a~%" x num))))
(defun isprime-p(n)
(defparameter isprime NIL)
(if (and (oddp n) (> n 2))
(loop for x from 2 below n
do (if (eql 0 (mod n x))
(progn (setq isprime NIL)
(return NIL))
(setq isprime T))))
(if (eq n 2)
(setq isprime T))
(print isprime))
(defun getprimes(lim)
(defparameter primes NIL)
(loop for x from 1 to lim
do (if (eql T (isprime-p x))
(push x primes)))
(print primes))
; Receive n input. Print nth Fibonacci number.
format PE console
entry start
include 'win32a.inc'
; ============================================
section '.text' code readable executable
start:
; The program begins here:
call read_hex
mov ecx, eax ; setup our counter, ecx.
dec ecx ; offset ecx counter.
mov ebx, 0 ; set ebx to 0. First Fib. num.
mov edx, 1 ; set edx to 1. Second Fib. num.
mov esi, 1 ; set esi to 1.
cmp eax, 0 ; if initial input is above 0, begin. Otherwise, exit.
ja fib
jmp exit
fib:
add ebx, edx ; Add to first terms (0 + 1)
mov edx, esi ; Put previous term into edx
mov esi, ebx ; Put previous sum into esi
dec ecx
;mov eax, esi
;call print_eax
cmp ecx, 0
jg fib ; Jump if GREATER to avoid failing comparing to FFFF...
; when ecx wraps back around below 0 after last dec.
; jg = signed. ja = unsigned.
mov eax, esi
call print_eax
exit:
; Exit the process:
push 0
call [ExitProcess]
include 'training.inc'
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Programming Language:
LISP
Solution:
(defun 3n5 (num)
(defparameter sum 0)
(loop for x from 1 below num do
(if (or (eq (mod x 3) 0) (eq (mod x 5) 0))
(setq sum (+ sum x))))
(format t "Sum of all multiples of 3 or 5 below ~a is: ~a~%" num sum))
Back in my early to mid-twenties, I worked as a night-auditor for a popular ocean-front resort in Montauk – the small town I grew up in. My main responsibility was to balance the entire days worth of business services against the money/credits/debits/etc… submitted by all revenue centers (Spa, Beach, Bar, Cafe, Hotel, Dining room and so on). This was one of the many “odd” jobs I found myself working and it was because of this job that I discovered a few pretty fascinating properties between the relationships certain types of numbers hold with one another. I’ve always had a passion for numbers and a natural proclivity for deeply understanding the things that interested me.
When working with numbers as a night-auditor your primary goal is to “check and balance”; to reconcile. When going about your job, it’s not uncommon to find transposition errors. A transposition error in accounting is when two or more adjacent digits or figures are reversed. These errors are very easy to spot because you’ll usually end up with a difference such that the amount out of balance is always evenly divisible by 9. For example, you tally up a stack of receipts knowing that the total amount has to equal, let’s say $320.89, but you end up with a total of $320.98 (89 cents to 98 cents), or your total needs to equal $181 but you somehow end up with $190. If you’ve crunched numbers long enough, you’re bound to run into this phenomena.
It wasn’t after probably a couple of years that one (very boring) night I decided to purposely make transposition errors and start jotting down how my intentional errors correlated to a deviation in my balance. In other words, I wanted to see exactly how by making these errors, if there was a way to understand more deeply the error itself and how, if at all, it related to anything else. I simply wanted more insight into this basic pattern I began to recognize. I did not know about this common accounting phenomena at the time nor any accounting “tricks” used to spot these types of errors. It fascinated me however, so I thought to investigate some more.
I began by making a simple chart (table 1) with random 2-digit numbers. I wrote down the intended number – meaning the correct number. The reverse of that number or what we’re calling the transposition error, and finally what the difference between these two numbers were.
Intended number
Transposition Error
Difference
19
91
72
34
43
9
73
37
36
41
14
27
82
28
54
74
47
27
57
75
18
95
59
36
29
92
63
Table 1
As we already know or what I later found out, is that the difference will always be evenly divisible by 9. This means that the difference will be a multiple of 9. I thought this was pretty neat but was there more? How do these numbers relate to each other besides the obvious in that their difference is always a multiple of 9? “Is there some deeper pattern?”, I asked myself. Well, there was. So I thought about how the difference between the intended number and the reverse of that number (transposition error) relate. Was there some information in the numbers themselves that could shine some light on the matter? I believed there was and so I looked a little closer.
If I take the number 91 by itself, what can that tell me about all the other information in my chart? Well, let’s see – 91 is made up of the digits 9 and 1. Okay, so what? Hmm, what does 9 and 1 tell me about 19 and the difference 72? What’s the pattern? Well, let’s play a little. Why not?
9 + 1 = 10
How does 10 relate to 72 ? … Nah, doesn’t really lead me anywhere obvious.
What about 9 – 1 = 8. How does 8 relate to 72 and 9 ? …
8 * 9 = 72. Okay, this seems like an interesting path to follow, let’s continue.
Looking back at my chart 91 – 19 = 72, or to get the reverse of 91 (19) we are exactly 72 units away. Another way to look at this is that we are 72/9 or 8, 9‘s apart.
I put the few things I found together and came up with my first steps towards an algorithm for 2-digit numbers.
91 is made up of the digits "9" and "1". If I take their difference I get "8".How does "8" relate to the difference between "91" and "19" or "72"? "8 x 9 = 72". This means that if I take the difference between the digits that make up either number "91" or "19" and ignore the sign (take absolute value), and multiply by the magical number "9", I'll have the difference between the original 2-digit number and its reverse!
At this point a general sense of euphoria rushes through my body as if I’ve discovered a little secret. As insignificant as it may be, a secret nonetheless! I felt as if I was somehow in direct contact with GOD. It was a great feeling to say the least. The beauty of what I had just discovered was that a lot of the information I found was inherent in the original number itself. It was as if the original number was packed with this secret information that just needed a little unraveling. Somewhat recursive if you will. This will make more sense later (I hope) when I try to generalize this discovery to 3-digits.
So now I see that from any single 2-digit number I can quickly figure out the difference between it and its reverse. Not just that it’s divisible by 9 but beyond that.
A common accounting mistake turns into a quick math “trick” you can use to impress your friends with Mental-Mathe-magic!
Algorithm for reversing any 2-digit number using the number 9 or how to quickly calculate the difference between any 2-digit number and its reverse:
1.) Pick any 2-digit number (ex: 38)
2.) Take the difference of the digits that make up the 2-digit number
and take its absolute value. (3 - 8 = -5), |-5| = 5
3.) Multiply the result from step 2 by 9 (5 * 9 = 45)
4.) If the first digit in the original 2-digit number is less than the
second digit, ADD the result of step 3, otherwise SUBTRACT.
(3 is less than 8 so, 38 + 45 = 83).
5.) Result of step 4 is always the reverse of original number from step 1.
I couldn’t contain myself. I shared this neat little trick with anyone that would listen and one night while I was explaining this to my future wife, I thought how I could do something similar with 3-digit numbers and what I had already learned.
This time around I didn’t have a chart so I just used my memory. For the purpose of making this easier to follow I’ll make a chart.
The chart would’ve looked something like the following:
Number
Reverse of Number
Difference
387
783
396
979
979
000
123
321
198
489
984
495
100
001
099
111
111
000
Table 2
It may not be so obvious, but there is a neat little pattern in the chart above. More on this pattern later. This time around I started with any 3-digit number and simply reversed it. I then took the difference and asked myself similar questions to those when I was investigating the 2-digit numbers and their reverse. The main question this time was how does the difference relate to the number 9? Why 9? because that was the magic number that made the last algorithm work. Why not this time?
I began trying to apply the same simple math rules and operations to the original 3-digit number and after some trial and error I discovered another pattern. My thought process went something like this:
Let’s start with any 3-digit number.
387
What happens if I take 3 – 8? Or 8 – 7? Or 3 – 7? Notice that I’m simply breaking apart the original 3-digit number 3 8 7 and running it through step 2 and on of my 2-digit algorithm.
Okay, so 45… How’s this relate to the difference between 387 and 783 or 369? Not seeing anything that sticks out here… Let’s try the second set of numbers.
We come to 36. This is a bit interesting isn’t it? Looks like the difference (369) but it’s missing a “9” in between the “3” and the “6“. Perhaps there’s something to this.
I continue down this path trying this method with several numbers and to my surprise I stumble across another neat little pattern.
I put together my findings and begin formulating another algorithm. This time for 3-digit numbers and their reverse or rather, their difference.
If I take the first and last digits of any 3-digit number and subtract them ignoring the sign (absolute value), then multiply the result by my magical number “9“, I always end up with something that looks like their difference except it’s missing a “9” right smack in the middle… Interesting.
“Could that be it?” I ask myself. Just subtract, multiply by “9” and insert a “9” in the middle of my product? Can’t be… I’m a little skeptical so I try to fudge up the process by picking numbers that may not play nice. A little something I learned as a programmer. I decide to try this with the numbers like “000“, “111“, “393”
1.) 000 -> 000 with a difference of 0.
2.) 0 (first digit "000") - 0 (last digit of "000") = 0
3.) |0| = 0
4.) 0 * 9 = 0, or 00
5.) 0 9 0
The result of “090” being the difference didn’t make sense… perhaps it’s an exception. Let’s keep going.
1.) 111 -> 111 with a difference of 0.
2.) 1 (first digit "111") - 1 (last digit of "111") = 0
3.) |0| = 0
4.) 0 * 9 = 0, or 00
5.) 0 9 0
This also didn’t make sense. Not surprising considering “000” and “111” are very similar numbers. What about the next one?
1.) 393 -> 393 with a difference of 0.
2.) 3 (first digit "393") - 3 (last digit of "393") = 0
3.) |0| = 0
4.) 0 * 9 = 0, or 00
5.) 0 9 0
Well, this didn’t make sense either. What could be the problem? Turns out to be very simple. Just look for the pattern. Whenever the first and the last numbers in my original 3-digit number are the same, the difference is 0. The 3-digit number basically “pivots” off the middle number when reversed. So if the original 3-digit number’s first digit is the same as the last, the reverse of that number is also the original and there will not be a difference! Okay, all clear.
That takes care of all the 3-digit numbers that are palindromes 😉 What about the others?
Let’s try “102“, “225“, “907“
1.) 102-> 201 with a difference of 99.
2.) 1 (first digit "102") - 2 (last digit of "102") = -1
3.) |-1| = 1
4.) 1 * 9 = 1, or 09
5.) 0 9 9
Neat! it works. What about the other two 3-digit numbers?
1.) 225-> 522 with a difference of 297.
2.) 2 (first digit "225") - 5 (last digit of "225") = -3
3.) |-3| = 3
4.) 3 * 9 = 27
5.) 2 9 7
Oh cool! that works too. That last one?
1.) 907-> 709 with a difference of 198.
2.) 9 (first digit "907") - 7 (last digit of "907") = 2
3.) |2| = 2
4.) 2 * 9 = 18
5.) 1 9 8
Yup! it checks out. It seems I now have my second algorithm.
Algorithm for determining the difference between any 3-digit number and its reverse:
1.) Pick any 3-digit number whose first and last digits are not the same.
If they are, result is 0. (ex: 358)
2.) Take the difference of the first and last digits that make up the
3-digit number and take its absolute value. (3 - 8 = -5), |-5| = 5
3.) Multiply the result from step 2 by 9 (5 * 9 = 45)
4.) Take your result from step 3 and insert the number 9 between
the digits in the product. (495).
5.) Result of step 4 is always the difference between original number
from step 1 and its reverse.
And this is where I stopped. What started out as a simple curiosity became an exciting and educational experience with numbers but most importantly, a somewhat spiritual journey as well. I developed a deep connection to my discoveries. Few things in this world have given me such a pure spiritual/emotional feeling than this has. Nothing beats the sensation of discovering something new for yourself without prior knowledge of the matter. I plan to continue my journey deeper into this little rabbit hole I began exploring decades ago. Perhaps it will lead me somewhere pure again. I’m sure it will 🙂