Two Simple Tasks

January 5, 2021

Happy New Year! May 2021 be a better year than 2020.

We have two simple tasks today:

First: Write a program that prints the sequence 1, 5, 10, 50, 100, … up to a given limit.

Second: Write a program that finds all three-digit numbers n such that n/11 equals the sum of the squares of the three digits.

Your task is to write programs that solve the two tasks given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

10 Responses to “Two Simple Tasks”

  1. chaw said

    I felt like generalizing the first problem a bit and am including my
    solution in standard R7RS Scheme below, along with a simple solution
    to the second one as well. Happy 2021 to all!

    (import (scheme base)
            (scheme write)
            (only (srfi 1)
                  circular-list every)
            (srfi 8))
    
    (define-syntax assert
      (syntax-rules ()
        ((_ pred ...) (unless (and pred ...)
                        (display "Failed assertion: ")
                        (display '(pred ...))
                        (newline)
                        (error "assertion failure"))))) 
    
    (define (multi-geometric-progression-fold kons knil init multipliers limit)
      (assert (number? init) (pair? multipliers) (every number? multipliers))
      (let f ((seed knil)
              (term init)
              (muls (apply circular-list multipliers)))
        (if (>= term limit)
            seed
            (f (kons term seed)
               (* term (car muls))
               (cdr muls)))))
    
    (assert (equal? '(1000 500 100 50 10 5 1)
                    (multi-geometric-progression-fold cons '() 1 '(5 2) 1001)))
    
    (assert (equal? '(1008 1008 252 252 84 84 21 21 7)
                    (multi-geometric-progression-fold cons '() 7 '(3 1 4 1) 2001)))
    
    (assert (equal? '(10000 5000 1000 500 100 50 10 5 1)
                    (multi-geometric-progression-fold cons '() 1 '(5 2) 10001)))
    
    (define (digits n)
      (if (zero? n)
          '(0)
          (let f ((n n)
                  (digits '()))
            (if (zero? n)
                digits
                (receive (quot rem) (floor/ n 10)
                  (f quot
                     (cons rem digits)))))))
    
    (define (q2)
      (let f ((n 110)
              (m 10) ; n/11 = m
              (r '()))
        (if (> n 999)
            (reverse r)
            (f (+ n 11)
               (+ m 1)
               (if (= m (apply + (map square (digits n))))
                   (cons n r)
                   r)))))
    
    (assert (equal? '(550 803) (q2)))
    

  2. (defun 5-1-sequence (limit)
      (cons 1 (loop :for f := t :then (not f)
                    :for n := 5 :then (* (if f 5 2) n)
                    :while (< n limit)
                    :collect n)))
    
    (assert (equalp (5-1-sequence 100001)
                    '(1 5 10 50 100 500 1000 5000 10000 50000 100000)))
    
    (defun print-5-1-sequence (limit)
      (let ((*print-right-margin* 72))
        (pprint (5-1-sequence limit)))
      (values))
    
    (print-5-1-sequence 10000001)
    
    ;; (1 5 10 50 100 500 1000 5000 10000 50000 100000 500000 1000000 5000000
    ;;  10000000)
    
    
    (defun find-numbers (min max such-as)
      (loop
        :for i :from min :to max
        :when (funcall such-as i)
          :collect i))
    
    (defun square (x) (* x x))
    
    (assert (equalp (find-numbers 0 999
                                  (lambda (n)
                                    (let ((a (truncate n 100))
                                          (b (mod (truncate n 10) 10))
                                          (c (mod n 10)))
                                      (= (/ n 11)
                                         (+ (square a) (square b) (square c))))))
                    '(0 550 803)))
    
  3. Zack said

    Such a good way to start the new coding year :-) Here is my take on this drill using Julia 1.5.2: https://pastebin.com/AjpJg1Hn. Cheers

  4. Daniel said

    Here’s a solution to the first task in x86-64 assembly using Linux system calls.

    ; sequence.asm
    
    ; Description
    ;   Print the sequence 1, 5, 10, 50, 100, ... up to the specified limit
    ; Synopsis
    ;   ./sequence LIMIT
    ; Build
    ;   nasm -felf64 sequence.asm
    ;   ld -o sequence sequence.o
    ; Warning
    ;   Overflow and invalid input is not checked/handled
    
      global _start
    
      section .text
    _start:
      ; make sure there is single argument
      cmp qword [rsp], 2
      jne exit_failure
      ; load argument as integer into rax then r8
      mov rax, 0 ; limit
      mov r8, [rsp + 16] ; address of next digit
      mov r9, 10
    atoi:
      movzx r10, byte [r8]
      cmp r10, 0
      je atoi_end
      mul r9
      sub r10, 48
      add rax, r10
      add r8, 1
      jmp atoi
    atoi_end:
      mov r8, rax ; limit
      mov r9, 1 ; current value
      ; r10 and r12 multipliers are swapped on each iteration
      ; skipped r11 since it's clobbered by syscall below
      mov r10, 5
      mov r12, 2
    main_loop:
      cmp r9, r8
      jg exit_success
      ; print r9
      mov rax, r9
      mov rbp, rsp
      sub rsp, 1
      mov byte [rsp], `\n`
      mov r13, 1 ; number of bytes
    digit_loop:
      xor rdx, rdx
      mov r14, 10
      div r14
      add r13, 1
      sub rsp, 1
      add rdx, 48
      mov [rsp], dl
      cmp rax, 0
      jne digit_loop
      mov rax, 1 ; write system call
      mov rdi, 1 ; stdout
      mov rsi, rsp ; address of string
      mov rdx, r13 ; number of bytes
      syscall
      mov rsp, rbp
      mov rax, r9
      mul r10
      mov r9, rax
      ; swap r10 and r12 using xor
      xor r10, r12
      xor r12, r10
      xor r10, r12
      jmp main_loop
    exit_failure:
      mov rdi, 1
    exit_success:
      xor rdi, rdi
      ; intentional fallthrough
    exit:
      mov rax, 60 ; exit system call
      syscall
    

    Example usage:

    $ ./sequence 9999
    1
    5
    10
    50
    100
    500
    1000
    5000
    
  5. Daniel said

    Here’s a solution to the second task in x86-64 assembly using Linux system calls.

    ; search.asm
    
    ; Description
    ;   Find all three digit numbers whose squared digits sum to the number divided
    ;   by 11
    ; Synopsis
    ;   ./search
    ; Build
    ;   nasm -felf64 search.asm
    ;   ld -o search search.o
    
      global _start
    
      section .text
    _start:
      mov r8, 110 ; current number
      mov r9, 10 ; current number divided by 11
      mov r10, 10 ; radix
    loop:
      cmp r8, 1000
      jge exit
      mov r11, 0 ; sum of digits
      mov rcx, 3
      mov r12, r8 ; workspace for extracting digits
    digit_loop:
      xor rdx, rdx
      mov rax, r12
      div r10
      mov r12, rax
      mov rax, rdx
      mul rax
      add r11, rax
      loop digit_loop
      cmp r11, r9
      jne continue_loop
      mov r12, r8
      mov r13, `\n`
      mov rcx, 3
    print_loop:
      xor rdx, rdx
      mov rax, r12
      div r10
      add rdx, 48
      shl r13, 8
      or r13, rdx
      mov r12, rax
      loop print_loop
      push r13
      mov rax, 1 ; write system call
      mov rdi, 1 ; stdout
      mov rsi, rsp ; address of string
      mov rdx, 4 ; number of bytes
      syscall
      sub rsp, 8
    continue_loop:
      add r8, 11
      add r9, 1
      jmp loop
    exit:
      xor rdi, rdi
      mov rax, 60 ; exit system call
      syscall
    

    Example usage:

    $ ./search
    550
    803
    
  6. Jan Van lent said

    A Lua solution for the first task.

    function print_seq(N)
       local i = 1
       while true do
          if i <= N then print(i) else break end
          i = i*5
          if i <= N then print(i) else break end
          i = i*2
       end
    end
    
    print_seq(500)
    
  7. Jan Van lent said

    Lua solution for the first task using mutual tail calls.

    function print_seq1(i, N)
       if i <= N then
          print(i)
          print_seq5(5*i, N)
       end
    end
    
    function print_seq5(i, N)
       if i <= N then
          print(i)
          print_seq1(2*i, N)
       end
    end
    
    print_seq1(1, 500)
    
  8. Jan Van lent said

    Lua solution for the second task. Brute force stepping through all the numbers from 100 to 999 rather than just multiples of 11. This allows interpreting n/11 as floor division (see commented line), giving more solutions.

    for d0 = 0, 9 do
       for d1 = 0, 9 do
          for d2 = 1, 9 do
    	 n = d2*100 + d1*10 + d0
    	 --m = math.floor(n/11)
    	 m = n / 11
    	 sumsq = d2^2 + d1^2 + d0^2
    	 if m == sumsq then
    	    print(n, sumsq)
    	 end
          end
       end
    end
    
  9. Kevin Short said

    A response for “Two Simple Tasks”, written in Racket:

    (define (print-comma-sep-list data)
      (let loop ([str "~a"] [li data])
        (cond
          [(empty? li) (printf ".\n")]
          [else (printf str (first li))
                (loop ", ~a" (rest li))])))
    
    (define (simp-task-1 lim)
      (let loop ([mult 1] [seed 1] [ans '()])
        (let ((val (* mult seed)))
          (if (<= val lim)
              (loop (if (equal? seed 5) (* mult 10) mult) (if (equal? seed 1) 5 1) (cons val ans))
              (print-comma-sep-list (reverse ans))))))
    
    (define (simp-task-2)
      (for ([i (in-range 100 1000)])
        (cond
          [(equal?
            (/ i 11)
            (foldl (lambda (s v) (+ (expt (string->number (list->string (list s))) 2) v))
                   0
                   (string->list (number->string i))))
           (printf "~a\n" i)])))
    


    And here are the results:

    Welcome to DrRacket, version 7.9 [3m].
    Language: racket, with debugging; memory limit: 128 MB.
    > (simp-task-1 500000)
    1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000, 500000.
    > (simp-task-2)
    550
    803
    > 
    

  10. Adam Beguelin said

    I’m trying to learn JavaScript. So here are my answers written in JS and run with node…

    var start = [“1”, “50”]

    function addzero(t) {
    return [t[0] += ‘0’, t[1] += ‘0’]
    }

    let max = 1000000
    for (var i = 0; i < 10; i++) {
    var r = addzero(start)
    if (r[0] > max || r[1] > max) return
    console.log(r.shift(),r.shift())
    }

    // prax1.js

    for (let i = 100; i < 1000; i++) {
    let d = i.toString().split(”)
    let dig = d.map(Number)
    let sum = dig[0] * dig[0] + dig[1]* dig[1] + dig[2] * dig[2]
    if (i/11 == sum) console.log(i/11, dig, sum)
    }

    % node prax1.js
    50 [ 5, 5, 0 ] 50
    73 [ 8, 0, 3 ] 73

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: