Divisibility of Fibonacci numbers sum
Statement
Goal
Sum of consecutive big Fibonacci numbers is divisible or not?Let a, b and d non negative integers.
Determine if d divides F_a + F_{a+1} + F_{a+2} + … + F_b.
The difficulty is that we ask that for some very big indices a.
Remember that the well-known Fibonacci numbers is a sequence of numbers starting with 0 and 1, and after that each number is the sum of the two previous ones.
F_0 =
F_1 =
F_{n+2} = F_{n+1} + F_n
So the first Fibonacci numbers are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…
Example:
a = 10
b = 12
F_10 + F_11 + F_12 = 55 + 89 + 144 = 288 = 32 * 9 = 2^5 * 3^2
This sum is divisible by d = 2, 4, 8, 16 and 32, but NOT by 64.
This sum is divisible by d = 3 and 9, but NOT by 27.
This sum is NOT divisible by d = 5.
This sum is divisible by d = 6.
…
Example of input:
2
10 12 3
10 12 5
And the expected output:
F_10 + ... + F_12 is divisible by 3
F_10 + ... + F_12 is NOT divisible by 5
(When a = b write in the same way the beginning "F_a + ... + F_b"
even if there is only one term.)
Hints:
Implementations of Fibonacci numbers computation is an usual example about recursivity and algorithmic complexity. The obvious way to implement it with recursion is a classical example of complexity explosion. There is several way to fix that, and the most obvious is the simple iteration that compute the result in a linear number of steps (if we consider that operations on numbers are in constant time, which is not really the case). The key point to solve this challenge is to find a mathematical way to be better than that and to implement it.
To help you can read the "Matrix form" section in "Fibonacci number" article on Wikipedia:
https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
Maybe this list of the first 300 Fibonacci numbers and their factorization can help you:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html#100
But if you need these big numbers, you are probably on a wrong way. ;-)
Enjoy!
(If you are interested by the mathematical aspect, there exist a lot of nice properties about this sequence:
https://oeis.org/A000045 )
(The illustration image is a part of one page of the Liber Abaci:
https://commons.wikimedia.org/wiki/File:Liber_abbaci_magliab_f124r.jpg )
Input
Line 1: An non negative integer nb for the number of tests.
Next nb lines: Three space separated non negative integers a, b and d for the first index, for the last index, and for the divisor.
Next nb lines: Three space separated non negative integers a, b and d for the first index, for the last index, and for the divisor.
Output
nb lines:
"F_a + ... + F_b is divisible by d"or
"F_a + ... + F_b is NOT divisible by d"
Constraints
b - a ≤
Example
Input
13 10 12 2 10 12 32 10 12 64 10 12 3 10 12 9 10 12 27 10 12 5 10 12 7 10 12 11 10 12 287 10 12 288 10 12 289 10 12 1000
Output
F_10 + ... + F_12 is divisible by 2 F_10 + ... + F_12 is divisible by 32 F_10 + ... + F_12 is NOT divisible by 64 F_10 + ... + F_12 is divisible by 3 F_10 + ... + F_12 is divisible by 9 F_10 + ... + F_12 is NOT divisible by 27 F_10 + ... + F_12 is NOT divisible by 5 F_10 + ... + F_12 is NOT divisible by 7 F_10 + ... + F_12 is NOT divisible by 11 F_10 + ... + F_12 is NOT divisible by 287 F_10 + ... + F_12 is divisible by 288 F_10 + ... + F_12 is NOT divisible by 289 F_10 + ... + F_12 is NOT divisible by 1000
Tags
Recursion, Loops, Arithmetic, Modular calculus
Difficulty
Hard
Test cases
First example Test
Input
13
10 12 2
10 12 32
10 12 64
10 12 3
10 12 9
10 12 27
10 12 5
10 12 7
10 12 11
10 12 287
10 12 288
10 12 289
10 12 1000
Output
F_10 + ... + F_12 is divisible by 2
F_10 + ... + F_12 is divisible by 32
F_10 + ... + F_12 is NOT divisible by 64
F_10 + ... + F_12 is divisible by 3
F_10 + ... + F_12 is divisible by 9
F_10 + ... + F_12 is NOT divisible by 27
F_10 + ... + F_12 is NOT divisible by 5
F_10 + ... + F_12 is NOT divisible by 7
F_10 + ... + F_12 is NOT divisible by 11
F_10 + ... + F_12 is NOT divisible by 287
F_10 + ... + F_12 is divisible by 288
F_10 + ... + F_12 is NOT divisible by 289
F_10 + ... + F_12 is NOT divisible by 1000
Example Validator
Input
12
16 18 2
16 18 16
16 18 32
16 18 3
16 18 5
16 18 17
16 18 19
16 18 23
16 18 1000
16 18 5167
16 18 5168
16 18 5169
Output
F_16 + ... + F_18 is divisible by 2
F_16 + ... + F_18 is divisible by 16
F_16 + ... + F_18 is NOT divisible by 32
F_16 + ... + F_18 is NOT divisible by 3
F_16 + ... + F_18 is NOT divisible by 5
F_16 + ... + F_18 is divisible by 17
F_16 + ... + F_18 is divisible by 19
F_16 + ... + F_18 is NOT divisible by 23
F_16 + ... + F_18 is NOT divisible by 1000
F_16 + ... + F_18 is NOT divisible by 5167
F_16 + ... + F_18 is divisible by 5168
F_16 + ... + F_18 is NOT divisible by 5169
Other example Test
Input
24
0 10 1
0 10 1000
0 10 2
0 10 3
0 10 5
0 10 7
0 10 11
0 10 13
0 10 17
0 10 142
0 10 143
0 10 144
5 16 1
5 16 16
5 16 32
5 16 3
5 16 5
5 16 7
5 16 23
5 16 529
5 16 49
5 16 2575
5 16 2576
5 16 2577
Output
F_0 + ... + F_10 is divisible by 1
F_0 + ... + F_10 is NOT divisible by 1000
F_0 + ... + F_10 is NOT divisible by 2
F_0 + ... + F_10 is NOT divisible by 3
F_0 + ... + F_10 is NOT divisible by 5
F_0 + ... + F_10 is NOT divisible by 7
F_0 + ... + F_10 is divisible by 11
F_0 + ... + F_10 is divisible by 13
F_0 + ... + F_10 is NOT divisible by 17
F_0 + ... + F_10 is NOT divisible by 142
F_0 + ... + F_10 is divisible by 143
F_0 + ... + F_10 is NOT divisible by 144
F_5 + ... + F_16 is divisible by 1
F_5 + ... + F_16 is divisible by 16
F_5 + ... + F_16 is NOT divisible by 32
F_5 + ... + F_16 is NOT divisible by 3
F_5 + ... + F_16 is NOT divisible by 5
F_5 + ... + F_16 is divisible by 7
F_5 + ... + F_16 is divisible by 23
F_5 + ... + F_16 is NOT divisible by 529
F_5 + ... + F_16 is NOT divisible by 49
F_5 + ... + F_16 is NOT divisible by 2575
F_5 + ... + F_16 is divisible by 2576
F_5 + ... + F_16 is NOT divisible by 2577
Other example Validator
Input
25
4 19 1
4 19 3
4 19 9
4 19 5
4 19 7
4 19 49
4 19 11
4 19 521
4 19 271441
4 19 10940
4 19 10941
4 19 10942
0 12 1
0 12 1000
0 12 8
0 12 16
0 12 3
0 12 5
0 12 7
0 12 46
0 12 47
0 12 48
0 12 375
0 12 376
0 12 377
Output
F_4 + ... + F_19 is divisible by 1
F_4 + ... + F_19 is divisible by 3
F_4 + ... + F_19 is NOT divisible by 9
F_4 + ... + F_19 is NOT divisible by 5
F_4 + ... + F_19 is divisible by 7
F_4 + ... + F_19 is NOT divisible by 49
F_4 + ... + F_19 is NOT divisible by 11
F_4 + ... + F_19 is divisible by 521
F_4 + ... + F_19 is NOT divisible by 271441
F_4 + ... + F_19 is NOT divisible by 10940
F_4 + ... + F_19 is divisible by 10941
F_4 + ... + F_19 is NOT divisible by 10942
F_0 + ... + F_12 is divisible by 1
F_0 + ... + F_12 is NOT divisible by 1000
F_0 + ... + F_12 is divisible by 8
F_0 + ... + F_12 is NOT divisible by 16
F_0 + ... + F_12 is NOT divisible by 3
F_0 + ... + F_12 is NOT divisible by 5
F_0 + ... + F_12 is NOT divisible by 7
F_0 + ... + F_12 is NOT divisible by 46
F_0 + ... + F_12 is divisible by 47
F_0 + ... + F_12 is NOT divisible by 48
F_0 + ... + F_12 is NOT divisible by 375
F_0 + ... + F_12 is divisible by 376
F_0 + ... + F_12 is NOT divisible by 377
Big numbers Test
Input
25
32 85 43
20 100 4
32 85 45
20 100 3
32 85 2521
20 100 5
20 100 25
32 85 128
20 100 11
32 85 25
20 100 121
20 100 41
32 85 31
20 100 4577887
32 85 64
32 85 9
32 85 27
20 100 1174951
32 85 5
20 100 2
32 85 7
32 85 13
32 85 61
32 85 17
32 85 19
Output
F_32 + ... + F_85 is NOT divisible by 43
F_20 + ... + F_100 is NOT divisible by 4
F_32 + ... + F_85 is divisible by 45
F_20 + ... + F_100 is divisible by 3
F_32 + ... + F_85 is divisible by 2521
F_20 + ... + F_100 is divisible by 5
F_20 + ... + F_100 is NOT divisible by 25
F_32 + ... + F_85 is NOT divisible by 128
F_20 + ... + F_100 is divisible by 11
F_32 + ... + F_85 is NOT divisible by 25
F_20 + ... + F_100 is NOT divisible by 121
F_20 + ... + F_100 is divisible by 41
F_32 + ... + F_85 is divisible by 31
F_20 + ... + F_100 is divisible by 4577887
F_32 + ... + F_85 is divisible by 64
F_32 + ... + F_85 is divisible by 9
F_32 + ... + F_85 is NOT divisible by 27
F_20 + ... + F_100 is divisible by 1174951
F_32 + ... + F_85 is divisible by 5
F_20 + ... + F_100 is divisible by 2
F_32 + ... + F_85 is NOT divisible by 7
F_32 + ... + F_85 is NOT divisible by 13
F_32 + ... + F_85 is divisible by 61
F_32 + ... + F_85 is NOT divisible by 17
F_32 + ... + F_85 is divisible by 19
Big numbers Validator
Input
24
23 106 169
23 106 16
21 105 419
23 106 32
21 105 379
23 106 7
21 105 351
23 106 11
23 106 13
23 106 29
23 106 841
21 105 13
23 106 43
23 106 177241
23 106 5
21 105 2
23 106 9
21 105 4
21 105 27
21 105 81
21 105 11
23 106 27
21 105 421
21 105 10891
Output
F_23 + ... + F_106 is NOT divisible by 169
F_23 + ... + F_106 is divisible by 16
F_21 + ... + F_105 is NOT divisible by 419
F_23 + ... + F_106 is NOT divisible by 32
F_21 + ... + F_105 is divisible by 379
F_23 + ... + F_106 is NOT divisible by 7
F_21 + ... + F_105 is divisible by 351
F_23 + ... + F_106 is NOT divisible by 11
F_23 + ... + F_106 is divisible by 13
F_23 + ... + F_106 is divisible by 29
F_23 + ... + F_106 is NOT divisible by 841
F_21 + ... + F_105 is divisible by 13
F_23 + ... + F_106 is divisible by 43
F_23 + ... + F_106 is NOT divisible by 177241
F_23 + ... + F_106 is NOT divisible by 5
F_21 + ... + F_105 is divisible by 2
F_23 + ... + F_106 is divisible by 9
F_21 + ... + F_105 is NOT divisible by 4
F_21 + ... + F_105 is divisible by 27
F_21 + ... + F_105 is NOT divisible by 81
F_21 + ... + F_105 is NOT divisible by 11
F_23 + ... + F_106 is NOT divisible by 27
F_21 + ... + F_105 is divisible by 421
F_21 + ... + F_105 is divisible by 10891
Even big numbers Test
Input
23
123 234 343
123 234 2401
123 234 26013
123 234 3
123 234 78039
123 234 5
110 301 1024
123 234 103680
123 234 103682
123 234 20641
110 301 512
123 234 103681
110 301 1097
110 301 3167
211 398 43759
353 616 6561
211 398 43763
353 616 122464
353 616 5021024
211 398 81
353 616 19683
432 433 106998173
321 321 6
Output
F_123 + ... + F_234 is divisible by 343
F_123 + ... + F_234 is NOT divisible by 2401
F_123 + ... + F_234 is divisible by 26013
F_123 + ... + F_234 is divisible by 3
F_123 + ... + F_234 is NOT divisible by 78039
F_123 + ... + F_234 is NOT divisible by 5
F_110 + ... + F_301 is NOT divisible by 1024
F_123 + ... + F_234 is NOT divisible by 103680
F_123 + ... + F_234 is NOT divisible by 103682
F_123 + ... + F_234 is divisible by 20641
F_110 + ... + F_301 is divisible by 512
F_123 + ... + F_234 is divisible by 103681
F_110 + ... + F_301 is NOT divisible by 1097
F_110 + ... + F_301 is divisible by 3167
F_211 + ... + F_398 is NOT divisible by 43759
F_353 + ... + F_616 is divisible by 6561
F_211 + ... + F_398 is divisible by 43763
F_353 + ... + F_616 is divisible by 122464
F_353 + ... + F_616 is NOT divisible by 5021024
F_211 + ... + F_398 is NOT divisible by 81
F_353 + ... + F_616 is NOT divisible by 19683
F_432 + ... + F_433 is divisible by 106998173
F_321 + ... + F_321 is NOT divisible by 6
Even big numbers Validator
Input
23
121 240 32
121 240 2522
121 240 5
121 240 121
121 240 2521
121 240 31
121 240 25
121 240 11
121 240 6355441
102 305 8
121 240 81
102 305 16
121 240 61
121 240 281
345 602 17108701
102 305 9168377
345 602 500
121 240 2520
345 602 17165711
102 305 27505131
345 602 100
450 451 12854199
354 354 24
Output
F_121 + ... + F_240 is NOT divisible by 32
F_121 + ... + F_240 is NOT divisible by 2522
F_121 + ... + F_240 is divisible by 5
F_121 + ... + F_240 is NOT divisible by 121
F_121 + ... + F_240 is divisible by 2521
F_121 + ... + F_240 is divisible by 31
F_121 + ... + F_240 is NOT divisible by 25
F_121 + ... + F_240 is divisible by 11
F_121 + ... + F_240 is NOT divisible by 6355441
F_102 + ... + F_305 is divisible by 8
F_121 + ... + F_240 is NOT divisible by 81
F_102 + ... + F_305 is NOT divisible by 16
F_121 + ... + F_240 is divisible by 61
F_121 + ... + F_240 is divisible by 281
F_345 + ... + F_602 is divisible by 17108701
F_102 + ... + F_305 is divisible by 9168377
F_345 + ... + F_602 is NOT divisible by 500
F_121 + ... + F_240 is NOT divisible by 2520
F_345 + ... + F_602 is NOT divisible by 17165711
F_102 + ... + F_305 is NOT divisible by 27505131
F_345 + ... + F_602 is divisible by 100
F_450 + ... + F_451 is divisible by 12854199
F_354 + ... + F_354 is NOT divisible by 24
Larger indices Test
Input
16
1234 2345 4
3897 3910 54988205
1781 2444 9
1234 2345 6
1234 2345 36
3560 4013 15
1781 2444 2529
1234 2345 3
2123 4489 12810074
1234 2345 9
1234 2345 8
2123 4489 25620148
1234 2345 5
1234 2345 7
1234 2345 15
1781 2444 18
Output
F_1234 + ... + F_2345 is divisible by 4
F_3897 + ... + F_3910 is divisible by 54988205
F_1781 + ... + F_2444 is divisible by 9
F_1234 + ... + F_2345 is divisible by 6
F_1234 + ... + F_2345 is NOT divisible by 36
F_3560 + ... + F_4013 is NOT divisible by 15
F_1781 + ... + F_2444 is divisible by 2529
F_1234 + ... + F_2345 is divisible by 3
F_2123 + ... + F_4489 is divisible by 12810074
F_1234 + ... + F_2345 is NOT divisible by 9
F_1234 + ... + F_2345 is NOT divisible by 8
F_2123 + ... + F_4489 is NOT divisible by 25620148
F_1234 + ... + F_2345 is NOT divisible by 5
F_1234 + ... + F_2345 is NOT divisible by 7
F_1234 + ... + F_2345 is NOT divisible by 15
F_1781 + ... + F_2444 is NOT divisible by 18
Larger indices Validator
Input
14
1230 2343 32
1111 2222 68379666
2156 4860 15
3048 4482 12
1230 2343 1789
1230 2343 27
3604 6705 6158652
1230 2343 5
1230 2343 108
1111 2222 205138998
1230 2343 36
1230 2343 9
1230 2343 15
1230 2343 16
Output
F_1230 + ... + F_2343 is NOT divisible by 32
F_1111 + ... + F_2222 is divisible by 68379666
F_2156 + ... + F_4860 is NOT divisible by 15
F_3048 + ... + F_4482 is NOT divisible by 12
F_1230 + ... + F_2343 is divisible by 1789
F_1230 + ... + F_2343 is NOT divisible by 27
F_3604 + ... + F_6705 is divisible by 6158652
F_1230 + ... + F_2343 is NOT divisible by 5
F_1230 + ... + F_2343 is NOT divisible by 108
F_1111 + ... + F_2222 is NOT divisible by 205138998
F_1230 + ... + F_2343 is divisible by 36
F_1230 + ... + F_2343 is divisible by 9
F_1230 + ... + F_2343 is NOT divisible by 15
F_1230 + ... + F_2343 is divisible by 16
Even larger indices Test
Input
13
12345 23456 2
12345 23456 27
12378 64506 2659000
40045 70000 4023361
12345 23456 7
28090 34708 282609
21568 554433 1488436
12345 23456 81
12345 23456 5
34890 40566 243296
12345 23456 16
12345 23456 32
12345 23456 3
Output
F_12345 + ... + F_23456 is divisible by 2
F_12345 + ... + F_23456 is divisible by 27
F_12378 + ... + F_64506 is NOT divisible by 2659000
F_40045 + ... + F_70000 is divisible by 4023361
F_12345 + ... + F_23456 is NOT divisible by 7
F_28090 + ... + F_34708 is divisible by 282609
F_21568 + ... + F_554433 is divisible by 1488436
F_12345 + ... + F_23456 is NOT divisible by 81
F_12345 + ... + F_23456 is NOT divisible by 5
F_34890 + ... + F_40566 is NOT divisible by 243296
F_12345 + ... + F_23456 is divisible by 16
F_12345 + ... + F_23456 is NOT divisible by 32
F_12345 + ... + F_23456 is divisible by 3
Even larger indices Validator
Input
19
10347 60451 29
10347 60451 58
12347 23458 2
12347 23458 32
12347 23458 64
12347 23458 3
12347 23458 9
12347 23458 27
12347 23458 5
12347 23458 7
12347 23458 2207
12347 23458 2777
12347 23458 3167
20570 54895 72774368
20570 54895 145548736
34891 41254 218921379
34891 41254 656764137
39800 60456 861
39800 60456 4305
Output
F_10347 + ... + F_60451 is divisible by 29
F_10347 + ... + F_60451 is NOT divisible by 58
F_12347 + ... + F_23458 is divisible by 2
F_12347 + ... + F_23458 is divisible by 32
F_12347 + ... + F_23458 is NOT divisible by 64
F_12347 + ... + F_23458 is divisible by 3
F_12347 + ... + F_23458 is divisible by 9
F_12347 + ... + F_23458 is NOT divisible by 27
F_12347 + ... + F_23458 is NOT divisible by 5
F_12347 + ... + F_23458 is NOT divisible by 7
F_12347 + ... + F_23458 is divisible by 2207
F_12347 + ... + F_23458 is divisible by 2777
F_12347 + ... + F_23458 is divisible by 3167
F_20570 + ... + F_54895 is divisible by 72774368
F_20570 + ... + F_54895 is NOT divisible by 145548736
F_34891 + ... + F_41254 is divisible by 218921379
F_34891 + ... + F_41254 is NOT divisible by 656764137
F_39800 + ... + F_60456 is divisible by 861
F_39800 + ... + F_60456 is NOT divisible by 4305
Become really big Test
Input
20
654321 987654 4
489 1005 258282
654321 987654 3
2468 897089 74400513
654321 987654 55592635
654321 987654 17
489 1005 774846
654321 987654 5
48903 4680607 1399681
654321 987654 289
780613 980156 30
654321 987654 54289
48903 4680607 9797767
654321 987654 53
2468 897089 87927879
654321 987654 2809
654321 987654 11881
780613 980156 6
654321 987654 7647985
654321 987654 29717
Output
F_654321 + ... + F_987654 is NOT divisible by 4
F_489 + ... + F_1005 is divisible by 258282
F_654321 + ... + F_987654 is NOT divisible by 3
F_2468 + ... + F_897089 is divisible by 74400513
F_654321 + ... + F_987654 is NOT divisible by 55592635
F_654321 + ... + F_987654 is divisible by 17
F_489 + ... + F_1005 is NOT divisible by 774846
F_654321 + ... + F_987654 is NOT divisible by 5
F_48903 + ... + F_4680607 is divisible by 1399681
F_654321 + ... + F_987654 is NOT divisible by 289
F_780613 + ... + F_980156 is NOT divisible by 30
F_654321 + ... + F_987654 is NOT divisible by 54289
F_48903 + ... + F_4680607 is NOT divisible by 9797767
F_654321 + ... + F_987654 is divisible by 53
F_2468 + ... + F_897089 is NOT divisible by 87927879
F_654321 + ... + F_987654 is NOT divisible by 2809
F_654321 + ... + F_987654 is NOT divisible by 11881
F_780613 + ... + F_980156 is divisible by 6
F_654321 + ... + F_987654 is NOT divisible by 7647985
F_654321 + ... + F_987654 is divisible by 29717
Become really big Validator
Input
20
815 2064 37105079
815 2064 43851457
3189 789015 5242
3189 789015 15726
654317 987658 8
654317 987658 16
654317 987658 5
654317 987658 17
654317 987658 289
654317 987658 53
654317 987658 2809
654317 987658 109
654317 987658 11881
654317 987658 233
654317 987658 196925089
654317 987658 29717
654317 987658 883100089
654317 987658 37039
777666 905436 29186772
777666 905436 145933860
Output
F_815 + ... + F_2064 is divisible by 37105079
F_815 + ... + F_2064 is NOT divisible by 43851457
F_3189 + ... + F_789015 is divisible by 5242
F_3189 + ... + F_789015 is NOT divisible by 15726
F_654317 + ... + F_987658 is divisible by 8
F_654317 + ... + F_987658 is NOT divisible by 16
F_654317 + ... + F_987658 is NOT divisible by 5
F_654317 + ... + F_987658 is divisible by 17
F_654317 + ... + F_987658 is NOT divisible by 289
F_654317 + ... + F_987658 is divisible by 53
F_654317 + ... + F_987658 is NOT divisible by 2809
F_654317 + ... + F_987658 is divisible by 109
F_654317 + ... + F_987658 is NOT divisible by 11881
F_654317 + ... + F_987658 is divisible by 233
F_654317 + ... + F_987658 is NOT divisible by 196925089
F_654317 + ... + F_987658 is divisible by 29717
F_654317 + ... + F_987658 is NOT divisible by 883100089
F_654317 + ... + F_987658 is divisible by 37039
F_777666 + ... + F_905436 is divisible by 29186772
F_777666 + ... + F_905436 is NOT divisible by 145933860
Really huge Test
Input
13
987000000 987654321 6493915
123456789 123567900 8690943
523489014 528904156 121639
987000000 987654321 48533
987000000 987654321 3
987000000 987654321 2
523489014 528904156 364917
987000000 987654321 17
987000000 987654321 289
123456789 123567900 10373061
987000000 987654321 9349
987000000 987654321 34439
987000000 987654321 4021
Output
F_987000000 + ... + F_987654321 is NOT divisible by 6493915
F_123456789 + ... + F_123567900 is NOT divisible by 8690943
F_523489014 + ... + F_528904156 is divisible by 121639
F_987000000 + ... + F_987654321 is divisible by 48533
F_987000000 + ... + F_987654321 is NOT divisible by 3
F_987000000 + ... + F_987654321 is divisible by 2
F_523489014 + ... + F_528904156 is NOT divisible by 364917
F_987000000 + ... + F_987654321 is divisible by 17
F_987000000 + ... + F_987654321 is NOT divisible by 289
F_123456789 + ... + F_123567900 is divisible by 10373061
F_987000000 + ... + F_987654321 is divisible by 9349
F_987000000 + ... + F_987654321 is divisible by 34439
F_987000000 + ... + F_987654321 is divisible by 4021
Really huge Validator
Input
13
513489014 518904153 407935
513489014 518904153 482105
987123456 987654441 2
987123456 987654441 3
987123456 987654441 5
987123456 987654441 11
987123456 987654441 121
987123456 987654441 31
987123456 987654441 151
987123456 987654441 3001
987123456 987654441 12301
987123456 987654441 18451
987123456 987654441 987654441
Output
F_513489014 + ... + F_518904153 is divisible by 407935
F_513489014 + ... + F_518904153 is NOT divisible by 482105
F_987123456 + ... + F_987654441 is divisible by 2
F_987123456 + ... + F_987654441 is NOT divisible by 3
F_987123456 + ... + F_987654441 is divisible by 5
F_987123456 + ... + F_987654441 is divisible by 11
F_987123456 + ... + F_987654441 is NOT divisible by 121
F_987123456 + ... + F_987654441 is divisible by 31
F_987123456 + ... + F_987654441 is divisible by 151
F_987123456 + ... + F_987654441 is divisible by 3001
F_987123456 + ... + F_987654441 is divisible by 12301
F_987123456 + ... + F_987654441 is divisible by 18451
F_987123456 + ... + F_987654441 is NOT divisible by 987654441
Other really huge Test
Input
18
999000000 1000000000 15625
1000000000 1000000000 5
42 4894511 452240819
979000000 979002345 28883462
1000000000 1000000000 1953125
1000000000 1000000000 41
979000000 979002345 43325193
1000000000 1000000000 1681
999000000 1000000000 78125
1000000000 1000000000 3
999000000 1000000000 7
42 4894511 421051797
999000000 1000000000 11
1000000000 1000000000 9765625
1000000000 1000000000 1
999000000 1000000000 1681
1000000000 1000000000 7
1000000000 1000000000 11
Output
F_999000000 + ... + F_1000000000 is divisible by 15625
F_1000000000 + ... + F_1000000000 is divisible by 5
F_42 + ... + F_4894511 is divisible by 452240819
F_979000000 + ... + F_979002345 is divisible by 28883462
F_1000000000 + ... + F_1000000000 is divisible by 1953125
F_1000000000 + ... + F_1000000000 is divisible by 41
F_979000000 + ... + F_979002345 is NOT divisible by 43325193
F_1000000000 + ... + F_1000000000 is NOT divisible by 1681
F_999000000 + ... + F_1000000000 is NOT divisible by 78125
F_1000000000 + ... + F_1000000000 is divisible by 3
F_999000000 + ... + F_1000000000 is divisible by 7
F_42 + ... + F_4894511 is NOT divisible by 421051797
F_999000000 + ... + F_1000000000 is divisible by 11
F_1000000000 + ... + F_1000000000 is NOT divisible by 9765625
F_1000000000 + ... + F_1000000000 is divisible by 1
F_999000000 + ... + F_1000000000 is NOT divisible by 1681
F_1000000000 + ... + F_1000000000 is divisible by 7
F_1000000000 + ... + F_1000000000 is divisible by 11
Other really huge Validator
Input
18
666 1234561 15513751
666 1234561 18334433
978000000 978002345 10094978
978000000 978002345 35332423
998000000 1000000000 15625
998000000 1000000000 78125
998000000 1000000000 7
998000000 1000000000 11
998000000 1000000000 13
998000000 1000000000 41
998000000 1000000000 1681
1000000000 1000000000 1
1000000000 1000000000 3
1000000000 1000000000 5
1000000000 1000000000 1953125
1000000000 1000000000 9765625
1000000000 1000000000 7
1000000000 1000000000 11
Output
F_666 + ... + F_1234561 is divisible by 15513751
F_666 + ... + F_1234561 is NOT divisible by 18334433
F_978000000 + ... + F_978002345 is divisible by 10094978
F_978000000 + ... + F_978002345 is NOT divisible by 35332423
F_998000000 + ... + F_1000000000 is divisible by 15625
F_998000000 + ... + F_1000000000 is NOT divisible by 78125
F_998000000 + ... + F_1000000000 is divisible by 7
F_998000000 + ... + F_1000000000 is divisible by 11
F_998000000 + ... + F_1000000000 is divisible by 13
F_998000000 + ... + F_1000000000 is divisible by 41
F_998000000 + ... + F_1000000000 is NOT divisible by 1681
F_1000000000 + ... + F_1000000000 is divisible by 1
F_1000000000 + ... + F_1000000000 is divisible by 3
F_1000000000 + ... + F_1000000000 is divisible by 5
F_1000000000 + ... + F_1000000000 is divisible by 1953125
F_1000000000 + ... + F_1000000000 is NOT divisible by 9765625
F_1000000000 + ... + F_1000000000 is divisible by 7
F_1000000000 + ... + F_1000000000 is divisible by 11
Solution language
Solution
Stub generator input