61 lines
2.8 KiB
Markdown
61 lines
2.8 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4fc1000cf542c51000e
|
|||
|
|
title: 'Задача 399: Вільні від квадратів числа Фібоначчі'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302064
|
|||
|
|
dashedName: problem-399-squarefree-fibonacci-numbers
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Перші 15 чисел Фібоначчі це:
|
|||
|
|
|
|||
|
|
$$1,1,2,3,5,8,13,21,34,55,89,144,233,377,610.$$
|
|||
|
|
|
|||
|
|
8 і 144 не є вільними від квадратів: 8 можна розділити на 4, а 144 можна розділити на 4 чи 9.
|
|||
|
|
|
|||
|
|
Тож перші 13 числа Фібоначчі, вільні від квадратів, це:
|
|||
|
|
|
|||
|
|
$$1,1,2,3,5,13,21,34,55,89,233,377 \text{ and } 610.$$
|
|||
|
|
|
|||
|
|
$200$th число Фібоначчі, вільне від квадратів це: 971183874599339129547649988289594072811608739584170445. Останні 16 цифр цього числа: 1608739584170445, що у вигляді експоненціального запису може бути записане, як `9.7e53`.
|
|||
|
|
|
|||
|
|
Знайдіть $100\\,000\\,000$th вільне від квадрата число Фібоначчі. Дайте відповідь у вигляді рядка, де після його останніх 16 цифр стоїть кома, після якої надане число у вигляді експоненціального запису (округлене до однієї цифри після десяткової крапки). Для $200$th вільного від квадрата числа відповідь буде: `1608739584170445,9.7e53`
|
|||
|
|
|
|||
|
|
**Note:** для цієї проблеми, пам'ятайте, що для кожного простого числа $p$, перше число Фібоначчі, що ділиться на $p$ не ділиться на $p^2$ (згідно з гіпотезою Т. Уолла). Підтверджено, що для простих чисел $≤ 3 \times {10}^{15}$, проте це не було доведено для загальних чисел.
|
|||
|
|
|
|||
|
|
Якщо так трапляється, що гіпотеза є хибною, тоді не факт, що вірною відповіддю буде $100\\,000\\,000$th вільне від квадрата число Фібоначчі. Радше сказати, що це буде лише нижня ланка цього числа.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`squarefreeFibonacciNumbers()` має повернути рядок.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert(typeof squarefreeFibonacciNumbers() === 'string');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`squarefreeFibonacciNumbers()` має повернути рядок `1508395636674243,6.5e27330467`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(squarefreeFibonacciNumbers(), '1508395636674243,6.5e27330467');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function squarefreeFibonacciNumbers() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
squarefreeFibonacciNumbers();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|