How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Racket programming language

Table of Contents

Problem Statement

The objective is to write a function that finds the sum of all positive multiples of 3 or 5 below n. Show output for n = 1000. This is is the same as Project Euler problem 1. Extra credit: do this efficiently for n = 1e20 or higher.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Racket programming language

Source code in the racket programming language

#lang racket
(require math)

;;; A naive solution
(define (naive k)
  (for/sum ([n (expt 10 k)] 
            #:when (or (divides? 3 n) (divides? 5 n)))
    n))

(for/list ([k 7]) (naive k))


;;; Using the formula for an arithmetic sum
(define (arithmetic-sum a1 n Δa)
  ; returns a1+a2+...+an
  (define an (+ a1 (* (- n 1) Δa)))
  (/ (* n (+ a1 an)) 2))

(define (analytical k)
  (define 10^k (expt 10 k))
  (define (n d) (quotient (- 10^k 1) d))
  (+    (arithmetic-sum  3 (n  3)  3)
        (arithmetic-sum  5 (n  5)  5)
     (- (arithmetic-sum 15 (n 15) 15))))

(for/list ([k 20]) (analytical k))

'(0 23 2318 233168 23331668 2333316668 233333166668)
'(0
  23
  2318
  233168
  23331668
  2333316668
  233333166668
  23333331666668
  2333333316666668
  233333333166666668
  23333333331666666668
  2333333333316666666668
  233333333333166666666668
  23333333333331666666666668
  2333333333333316666666666668
  233333333333333166666666666668
  23333333333333331666666666666668
  2333333333333333316666666666666668
  233333333333333333166666666666666668
  23333333333333333331666666666666666668)

You may also check:How to resolve the algorithm Hailstone sequence step by step in the Ioke programming language
You may also check:How to resolve the algorithm Loop over multiple arrays simultaneously step by step in the Oz programming language
You may also check:How to resolve the algorithm Primality by Wilson's theorem step by step in the C programming language
You may also check:How to resolve the algorithm Isqrt (integer square root) of X step by step in the Factor programming language
You may also check:How to resolve the algorithm Constrained random points on a circle step by step in the Ring programming language