Here is a AutoLISP reverse problem. It is reverse problem as I don’t ask you for the solution but rather like to see if you instead can find what problem this is a solution for.
(defun h (n / c)
(cons n (reverse (cons 1
(while (/= 1 (setq n (if (= (rem n 2) 0)
(/ n 2) (+ (* 3 n) 1))))
(setq c (cons n c))))))
)
The exercise is to tell me what this function does and possibly refactor it. Leave a comment (comments with solutions will be posted later on).
UPDATE:
The Collatz conjecture is a conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers, or as wondrous numbers.
Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called "Half Or Triple Plus One", or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness.
No sequence has been found so far that does not reach the number 1.
The code above (not formatted to make it harder for you to read) will return the hailstone sequence for any given number.
See Collatz conjecture for more on the topic.
I like to format my AutoLisp code like this:
ReplyDelete(defun h (n / c)
(cons n
(reverse
(cons 1
(while
(/= 1
(setq n
(if
(=(rem n 2) 0)
(/ n 2)
(+(* 3 n)1)
)
)
)
(setq c(cons n c))
)
)
)
)
)
This makes seeing the inner most set of parenthesis easy. And in this case the n passed is divided by 2 and if that equation has a remainder of 0 (zero) then that is the value returned. But if that equation fails the else statement is to then set n to 3 (three) its original value + (plus) 1 (one). Recursively the if and else values of the equations are found until the resulting value equals 1 (one).
Each value is added to a list that once the while loop is complete, is added to another list already defined with the value of 1 (one) in the first position. The order of the list is then reversed and added to another list already defined with the original value of n passed.
Here are the values this method returns when run with the numbers 1 - 15:
(h 1) = (1 4 2 1)
(h 2) = (2 1)
(h 3) = (3 10 5 16 8 4 2 1)
(h 4) = (4 2 1)
(h 5) = (5 16 8 4 2 1)
(h 6) = (6 3 10 5 16 8 4 2 1)
(h 7) = (7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
(h 8) = (8 4 2 1)
(h 9) = (9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
(h 10) = (10 5 16 8 4 2 1)
(h 11) = (11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
(h 12) = (12 6 3 10 5 16 8 4 2 1)
(h 13) = (13 40 20 10 5 16 8 4 2 1)
(h 14) = (14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
(h 15) = (15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1)
(h 16) = (16 8 4 2 1)
(h 17) = (17 52 26 13 40 20 10 5 16 8 4 2 1)
The description above is what the method does. But why write this method? What need does solve?
I thought maybe it has something to do with prime numbers. The highest number in each result, excluding the original value of n passed, is usually 1 (one) less than a prime number.
But then I noticed, like with the result of (h 9) = (9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1) that you could break down the results into groups as follow:
(9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
( 28 14 7 )
( 22 11 )
( 34 17 )
( 52 26 13 )
( 40 20 10 5 )
( 16 8 4 2 1)
Each of the groups starts with a prime number. I was almost ready to state that the method is for finding all the prime number less than the value of n, and their products no great than 3 (three) times n, but there are prime numbers great than n.
I give up on what is was written to do.
:)
Doug
Hi Doug,
ReplyDeletePlease find what the purpose of the code is in the updated post.
Heady stuff. :)
ReplyDelete