โจทย์: หาตำแหน่ง (index) ของตัวคูณของ K ที่เป็นตัวที่ N ใน Fibonacci Sequence
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
หาตำแหน่งของ multiple of K ที่เป็นตัวที่ N
คุณสมบัติ: Pisano Period / Divisibility
- ทุก K มี multiple ใน Fibonacci sequence (ทฤษฎี)
- Multiple ของ K ใน Fibonacci เกิดขึ้นเป็นระยะ (periodic)
- Index ของ multiple แรกของ K เรียกว่า Entry Point Z(K)
- Multiple ต่อๆ ไปอยู่ที่ index = m × Z(K) สำหรับ m = 1, 2, 3...
ตัวอย่างโค้ด (คำนวณ Entry Point แล้วคูณ N)
public class Demo {
// หา Entry Point Z(k) = index แรกที่ F(index) % k == 0
public static int findEntryPoint(int k) {
if (k == 1) return 1; // F(1) = 1
long a = 0, b = 1; // F(0), F(1)
for (int i = 2; ; i++) {
long c = (a + b) % k; // Modulo เพื่อป้องกัน overflow
if (c == 0) return i;
a = b;
b = c;
// Safety: Pisano period ≤ 6k
if (i > 6 * k) return -1; // ไม่ควรเกิด
}
}
// ตำแหน่งของ N-th multiple of K
public static long nthMultiplePosition(int n, int k) {
int entryPoint = findEntryPoint(k);
if (entryPoint == -1) return -1;
return 1L * n * entryPoint;
}
public static void main(String[] args) {
int n = 10; // 10th multiple
int k = 9; // of 9
int entry = findEntryPoint(k);
System.out.println("Entry point Z(" + k + ") = " + entry);
long pos = nthMultiplePosition(n, k);
System.out.println("Position of " + n + "th multiple of " + k + " = " + pos);
// Verify: compute Fibonacci at that position
System.out.println("F(" + pos + ") mod " + k + " = " + fibMod(pos, k));
}
static int fibMod(long n, int mod) {
if (n <= 1) return (int) n;
long a = 0, b = 1;
for (long i = 2; i <= n; i++) {
long c = (a + b) % mod;
a = b;
b = c;
}
return (int) b;
}
}
ผลลัพธ์
Entry point Z(9) = 12 Position of 10th multiple of 9 = 120 F(120) mod 9 = 0
คำอธิบาย: F(12) = 144 หาร 9 ลงตัว (144/9=16) เป็น multiple แรก Multiple ต่อไปอยู่ที่ 24, 36, 48... ตัวที่ 10 อยู่ที่ 12×10=120
Complexity
- Find Entry Point: O(k) (Pisano period ≤ 6k)
- Overall: O(k) time, O(1) space
