Project Euler: Problem 7

Challenge:

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'

Overview:

Coming soon…

Project Euler: Problem 6

Challenge:

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)))))

Overview:

Coming soon…

Project Euler: Problem 5

Challenge:

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().

Project Euler: Problem 4

Challenge:

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))

Overview:

Coming soon…

Project Euler: Problem 3

Challenge:

The prime factors of 13195 are 5, 7, 13 and 29.

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))

Overview:

Coming soon…

Project Euler: Problem 2

Challenge:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Programming Language:

LISP

Solution:

(defun fib-even-sum (fl)
  (if (<= (+ (car (reverse fl)) (cadr (reverse fl))) 4000000)
      (progn
	(push (+ (car (reverse fl)) (cadr (reverse fl))) (cdr (last fl)))
	(fib-even-sum fl)
	)
      )
  (apply #'+ (remove-if-not 'evenp fl))
  )

Overview:

Coming soon…


Programming Language:

x86 Assembly

Solution:

; 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'

Overview:

Coming soon…

Project Euler: Problem 1

Challenge:

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))

Overview:

Coming soon…

The magical number nine, or how I discovered a couple of interesting algorithms as a night-auditor.

– Click again to toggle Play/Stop.

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 numberTransposition ErrorDifference
199172
34439
733736
411427
822854
744727
577518
955936
299263
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:

NumberReverse of NumberDifference
387783396
979979000
123321198
489984495
100001099
111111000
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.

...
Step 2.) 3 - 8 = -5, |-5| = 5
Step 3.) 5 * 9 = 45

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.

...
Step 2.) 8 - 7 = 1, |1| = 1
Step 3.) 1 * 9 = 9

Here we have 9. Same question as before. Nothing sticks out here either. Let’s try the last group.

...
Step 2.) 3 - 7 = -4, |-4| = 4
Step 3.) 4 * 9 = 36

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 🙂