Least Common Multiple of Odds

Because of the Associative Laws of $lcm$ :

abs

and

gcd

we can use python's reduce function for constructing a rather short solution.

1
2

from fractions import gcd
print reduce(lambda a,b: a * b / gcd(a,b),range(1,100,2))

Note: The last 3 digits are 075, which is why the answer is displayed as 75.

First, I will think without any program language. Notice that the least common multiple of all odd numbers from 1 to 99 inclusive is equal to product of all prime numbers from 3 to 99 in a their proper degree, i.e. $LCM =3^{4}.5^{2}.7^{2}.11.13.17.19.23.29.31.37.41.43.47.53.59.61.67.71.73.79.83.89.97$ . This is easy to find if the all odd numbers are writing on one sheet and then make factorizing to non-prime of them. To get all prime it's easy to make an Eratosthenes' sieve.
The next steps are more identically. It's have to get the three last digits of each of following products in a sequence: $3^{4}.5^{2}.7^{2}=99225 \;and\; 99225≡225 (mod 1000);\\ \;Next\;\\ 225.11≡475 (mod 1000);\\475.13≡175(mod 1000);\\ 175.17≡975(mod 1000);\\ 975.19≡525(mod 1000);\\ 525.23≡75(mod 1000);\\ 75.29≡175 \;(mod1000)\\175.31≡425 \;(mod1000)\\425.37≡725 \;(mod1000)\\725.41≡725 \;(mod1000)\\725.43≡175 \;(mod1000)\\175.47≡225 \;(mod1000)\\225.53≡925 \;(mod1000)\\925.59≡575 \;(mod1000)\\575.61≡075 \;(mod1000)\\75.67≡025 \;(mod1000)\\25.71≡775 \;(mod1000)\\775.73≡575 \;(mod1000)\\575.79≡425 \;(mod1000)\\425.83≡275 \;(mod1000)\\275.89≡475 \;(mod1000)\\475.97≡075 \;(mod1000)\\ That\; is\; all:)!\;\\ But \;the\; above\; procedure\; can\; translate\; and \;execute\; with\; the\; computer.$

Before introducing the code, we should know that:

$\text{lcm}(a,b)\times \gcd(a,b)=|ab|$

$\displaystyle \text{lcm}(a,b)=\frac{|ab|}{\text{lcm}(a,b)}$

and

$\text{lcm}(a,b,c)=\text{lcm}(a,\text{lcm}(b,c))$

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from fractions import gcd
#We do this to get the gcd function

def lcm(a, b):
    return a * b // gcd(a, b)
"""
We have created a new lcm function.
Note that python doesn't built in lcm function so we should create it 
ourself with the usage of the relation between gcd and lcm.
However, this function can only support 2 numbers.
"""

def more_lcm(*args):
    return reduce(lcm, args)
"""
We have created a new function that can support more numbers.
The reduce part do something like lcm(a,b,c)=lcm(a, lcm(b,c)).
"""

print more_lcm(*range(1,99))/64
#Note that I divide the expression by 64 because we only want odd integers

The code should print out a very large number with the last three digit $\boxed{075}$ .

In Haskell:

foldl lcm 1 [3, 5 .. 99]

I've built a solution in Ruby (I'm more comfortable with it than Python, but if you know Python you should be able to understand everything without any problems). This problem's steps are basically finding the prime factors of all numbers from 1 to 99 and multiplying the different factors (choosing the biggest in case there are factors repeated). I've decided to build from scratch a method for each step (also some helper methods to find the primes). The solution is below, it's 97 lines long but I've tried to comment the code and make variables with names that reflect what they are storing. By the way, it seems that this editor does not support Ruby code, the text is very ugly even though it is marked as code. I've created a Gist for it: https://gist.github.com/otamm/5ba44cfc72df99dc08ea

def is_prime?(n,prime_array=false) # number to be checked as first parameter, optional second parameter to be used with the 'prime_array' method.
  if n < 2
    return false
  elsif n == 2
    return true
  else
    if prime_array
      for i in (2..(n/2)+1) #it makes no sense to divide by numbers which would result in a result less than 2 (the smallest prime); the '+1' in the end is due to the default 'round down' in integer division in Ruby.
          prime_array.each { |prime| return false if (n % prime) == 0 }
      end
    else
      for i in (2..(n/2)+1)
        if (n % i) == 0
          return false
        end
      end
    end
  end
  return true
end

def prime_array(n) #returns an array with all primes less than number n.
  if n < 2
    return []
  elsif n == 2
    return [2]
  else
    prime_array = [2]
    for i in (3..n)
      prime_array.push(i) if is_prime?(i,prime_array) # the own prime_array built so far is passed as an argument in order to improve processing speed.
    end
  end
  return prime_array
end

def prime_factors(n,biggest_number_prime_array=false) #returns the prime factors of a given number. if n is prime, returns n. second parameter to improve speed if method would be utilized in a range of numbers.
  factors = []
  if biggest_number_prime_array
    primes = biggest_number_prime_array
  else
    primes = prime_array(n)
  end

  while true
    signal = factors.size #signalizes when to break the loop.
    primes.each do |prime|
      if (n % prime) == 0
        factors.push(prime)
        n = n / prime
        break
      end
    end
    if signal == factors.size
      factors.push(n)
      break
    end
  end
  factors = factors.sort
  return factors - [1] #...because 1 is not a prime.
end

def lcm(nums) #method that returns the least common multiple between a given array of numbers.
  nums = nums.uniq.sort
  primes = prime_array(nums[-1]) #biggest number in the whole array.
  factorized_nums = [] #holds the prime factors for each value in nums array.
  nums.each { |n| factorized_nums.push(prime_factors(n,primes)) }

  unique_lcm_factors = [] #individual prime factors of lcm
  lcm_factors = {} #prime factors of lcm
  for factors in factorized_nums
    for factor in factors.uniq
      if lcm_factors.include?(factor)
        lcm_factors[factor] = factors.count(factor) if factors.count(factor) > lcm_factors[factor]
      else
        lcm_factors[factor] = factors.count(factor)
      end
    end
  end

  lcm = 1
  lcm_factors.each { |factor,max_quantity| lcm *= factor ** max_quantity }
  return lcm
end

# solution below
odds = []
for i in (1..99)
  odds.push(i) if (i % 2) == 1
end

lcm(odds)

# => 1089380862964257455695840764614254743075

Mathematica solution:

FromDigits[IntegerDigits[Apply[LCM, Range[1, 99, 2]]][[-3 ;;]]]

Using AutoHotkey and my Scientific Maths Library , this can be solved.

SetWorkingDir, % A_ScriptDir

t := 1
loop 50
  if IsPrime( n := (A_Index-1)*2+1 )
      t := SM_Multiply(t, n)
loop 4 
    t := SM_Multiply(t, A_index*2+1 )   ; taking odd squares like 9, 25, 49, 81

msgbox % t
return

IsPrime(n) {         ;by kon
    if (n < 2)
        return, 0
    else if (n < 4)
        return, 1
    else if (!Mod(n, 2))
        return, 0
    else if (n < 9)
        return 1
    else if (!Mod(n, 3))
        return, 0
    else {
        r := Floor(Sqrt(n))
        f := 5
        while (f <= r) {
            if (!Mod(n, f))
                return, 0
            if (!Mod(n, (f + 2)))
                return, 0
            f += 6
        }
        return, 1
    }
}

; https://github.com/aviaryan/autohotkey-scripts/blob/master/Functions/Maths.ahk
#include Maths.ahk

In Haskell:

foldl1 lcm $ filter odd [1..99]

This is my code in python. Just work for odd numbers below 100.

First, I listed primes below 100 except 2, they are all odd numbers. Second, adding some numbers that can be made by multiplying themselves 2 or more times. 27 came from 3x3x3x3 / 3 since I already added 3 to the prime list. 5 from 5x5 / 5. same thing can be said for 7. Finally, multiplying those numbers, also using modular arithmetic to prevent overflow.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

prime = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
addition = [27, 5, 7]          #[3*3*3, 5, 7 ]
prime = prime + addition
psize = len(prime)
primemult = 1
for i in range(psize):
  primemult *= prime[i]
  primemult %= 1000

print primemult