$1$'den $k$'ya kadar olan sayılara bölünebilen en küçük sayı nasıl bulunur?

Question

$k$ bir pozitif tam sayı olmak üzere, $1$'den $k$'ya kadar ($k$ sayısı da dahil) olan bütün tam sayılara bölünen en küçük pozitif tam sayı nasıl bulunur? Matematiksel alt yapısını, algoritmasını nasıl kurabiliriz?

Comments

1 den K ya kadar 2 tane iç içe for döngüsü işe yarayabilirmi acaba ?

---

hangi işlemlerle ?

---

eğer soruyu doğru anladıysam

{if mod = 0} kullanacağız.

zaten 0 ve 1 den başka sonuç alabiliyor muyuz k>2 için ?

---

tek for dongusu ile cozebilirsiniz.

sonuc = 1
for i in range(1,k):
    sonuc=ekok(sonuc,i)

 

---

Asagidaki @ece nin algoritmasinin Mathematica ile yazilisi

lcm[k_] := Times @@ Table[If [PrimeQ[i] == True, i^Floor[Log[k]/Log[i]],Nothing],{i, k}]

Gerci Mathematicanin LCM fonksiyonu direk kullanilabilir.

lcm2[k_] := LCM[Sequence @@ Range@k]

 

---

ben bu soruyu anladığımdan emin değilim ece hocam :)

 

vede kodlarımızı paylaşırken ,kod ile ilgili yorum satırı eklersek daha anlaşılır olabilir.

Answer 1

Aritmetiğin temel teoremi bize şunu söyler: "$1$'den büyük her doğal sayı, sonlu sayıda birtakım asal sayının pozitif kuvvetlerinin çarpımı şeklinde yazılır. Bu yazılış tek türlüdür."

Bu fikirden yola çıkarak devam etmek istiyorum. Sorudaki elde etmeye çalıştığımız sayı $A$ olsun. Aritmetiğin temel teoreminden, $A=p_1^{a_1} \cdots p_n^{a_n}$ olacak şekilde tek türlü $p_1 , \dots ,p_n$ asal sayıları ve $i=\overline{1,n}$ , $a_i >0$ sayıları vardır. Bu $p_i$'lere karşılık gelen $a_i$ leri belirlemeye çalışalım. $p_i^{a_i}=t$ ise $a_i\log(p_i)=\log(t)$ dir. Düzenlersek $a_i = \dfrac{\log(t)}{\log(p_i)}$ olur. Buradan şu yorumu yapabiliriz. Verilen bir $k$ sayısından küçük eşit herhangi bir asala baktığımızda,bu asalın en büyük kaçıncı kuvvetinin $k$ dan küçük eşit kaldığını logaritmalı yaptığımız işlemle bulabiliriz.

Örneğin $k=30$ ve $p=3$ için, $\dfrac{\log(30)}{\log(3)}=3.095\cdots$ dir. Yani $3$'ün $30$'dan küçük eşit kalacak şekilde en büyük tam kuvveti $\dfrac{\log(30)}{\log(3)}=3.095\cdots$ nin tam kısmı olan $3$ olur.

Soruya geri dönersek $k$'dan küçük eşit olan bütün $p_i$ asal sayıları için $a_i$'leri yukarıdaki gibi hesapladığımızda, $1$'den $k$'ya kadar olan bütün sayılara bölünebilen en küçük sayı $p_1^{a_1} \cdots p_n^{a_n}$ olur.

import math

def is_prime(n) :
    for i in range(2,int(n**0.5)+1) :
        if n % i == 0 :
            return False
    return True


k=int(input("k degerini girin:"))
i=2
A=1

while i <= k :
    if is_prime(i) :
        a = int(math.log(k) / math.log(i))
        A = A * (i**a)
    i += 1

print(A)

 

Answer 2

$k$ ya kadar olan butun sayilari yazalim. sonuc adli bir degiskenimiz olsun ve degeri $1$ olsun. Listenin en kucuk elemanini listeden cikarip  sonuc  un $ekok$ unu sonuca  atayalim. Bu islemi liste bitene kadar yaparsak elimize sonuc gececek. Bu islemi bir for dongusu ile yapabiliriz ama Haskell ve Python gibi dillerde bu isi yapan bir fonksiyon var bizim icin. Iki girdili bir fonksiyonu listenin elemanlarina son girdisini hatirlayacak sekilde sirayla uygulayan fonksiyon un adi reduce.

from functools import reduce
from math import gcd

def ekok(a, b):
    return abs(a*b) // gcd(a, b)

def cozum(k):
    return reduce(ekok,range(1,k+1))

def test(m):
    a = cozum(m)
    for i in range(1,m+1):
        print( str(a) + " % " + str(i) + " == " + str(a%i))
    

.