1
|
|
|
""" |
2
|
|
|
:mod:`tests.unit.test_numbertheory` -- Unit Tests |
3
|
|
|
================================================= |
4
|
|
|
|
5
|
|
|
.. module:: tests.unit.test_numbertheory |
6
|
|
|
:synopsis: Unit tests for the lib.numbertheory package. |
7
|
|
|
|
8
|
|
|
.. moduleauthor:: Bill Maroney <[email protected]> |
9
|
|
|
""" |
10
|
|
|
|
11
|
|
|
from collections import Counter |
12
|
|
|
from itertools import takewhile |
13
|
|
|
import pytest |
14
|
|
|
from random import choice, randint |
|
|
|
|
15
|
|
|
from typing import Optional, Union |
|
|
|
|
16
|
|
|
|
17
|
|
|
from lib.util import load_dataset |
18
|
|
|
from lib.numbertheory import is_even, is_odd, is_square |
19
|
|
|
from lib.numbertheory import divisor_count, divisor_sum, divisor_sum_aliquot |
20
|
|
|
from lib.numbertheory import is_probably_prime, prime_sieve, divisors_sieve |
21
|
|
|
from lib.numbertheory.primality import miller_rabin |
22
|
|
|
from lib.numbertheory.sieve import eratosthenes, segmented_eratosthenes |
23
|
|
|
from lib.numbertheory import factor |
24
|
|
|
from lib.numbertheory.factorisation import perfect_power_exponent |
25
|
|
|
|
26
|
|
|
|
27
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(0, True), (1, False), (200, True), (-123, False), (-24, True)]) |
|
|
|
|
28
|
|
|
def test_is_even_correctness(value: int, expected_answer: bool): |
29
|
|
|
""" Test the correctness of :func:`lib.numbertheory.is_even` using known answer tests |
30
|
|
|
|
31
|
|
|
:param value: the input value |
32
|
|
|
:param expected_answer: the expected answer |
33
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_even` returns the wrong type |
34
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_even` returns the wrong value |
35
|
|
|
""" |
36
|
|
|
|
37
|
|
|
computed_answer = is_even(value) |
38
|
|
|
assert isinstance(computed_answer, is_even.__annotations__["return"]), "wrong type" |
39
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
40
|
|
|
|
41
|
|
|
|
42
|
|
|
def test_is_even_bad_n_type_str(): |
43
|
|
|
""" Test that :func:`lib.numbertheory.is_even` raises a ``TypeError`` for a non-``int`` value for `n` (``str``) """ |
|
|
|
|
44
|
|
|
with pytest.raises(TypeError): |
45
|
|
|
is_even("123") |
46
|
|
|
|
47
|
|
|
|
48
|
|
|
def test_is_even_bad_n_type_float(): |
49
|
|
|
""" Test that :func:`lib.numbertheory.is_even` raises a ``TypeError`` for a non-``int`` value for `n` (``float``) |
|
|
|
|
50
|
|
|
""" |
51
|
|
|
with pytest.raises(TypeError): |
52
|
|
|
is_even(123.0) |
53
|
|
|
|
54
|
|
|
|
55
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(0, False), (1, True), (200, False), (-123, True), (-24, False)]) |
|
|
|
|
56
|
|
|
def test_is_odd_correctness(value: int, expected_answer: bool): |
57
|
|
|
""" Test the correctness of :func:`lib.numbertheory.is_odd` using known answer tests |
58
|
|
|
|
59
|
|
|
:param value: the input value |
60
|
|
|
:param expected_answer: the expected answer |
61
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_odd` returns the wrong type |
62
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_odd` returns the wrong value |
63
|
|
|
""" |
64
|
|
|
|
65
|
|
|
computed_answer = is_odd(value) |
66
|
|
|
assert isinstance(computed_answer, is_odd.__annotations__["return"]), "wrong type" |
67
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
68
|
|
|
|
69
|
|
|
|
70
|
|
|
def test_is_odd_bad_n_type_str(): |
71
|
|
|
""" Test that :func:`lib.numbertheory.is_odd` raises a ``TypeError`` for a non-``int`` value for `n` (``str``) """ |
|
|
|
|
72
|
|
|
with pytest.raises(TypeError): |
73
|
|
|
is_odd("123") |
74
|
|
|
|
75
|
|
|
|
76
|
|
|
def test_is_odd_bad_n_type_float(): |
77
|
|
|
""" Test that :func:`lib.numbertheory.is_odd` raises a ``TypeError`` for a non-``int`` value for `n` (``float``) """ |
|
|
|
|
78
|
|
|
with pytest.raises(TypeError): |
79
|
|
|
is_odd(123.0) |
80
|
|
|
|
81
|
|
|
|
82
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(0, True), (1, True), (122, False), (16, True), (10000, True)]) |
|
|
|
|
83
|
|
|
def test_is_square_correctness(value: int, expected_answer: bool): |
84
|
|
|
""" Test the correctness of :func:`lib.numbertheory.is_square` using known answer tests |
85
|
|
|
|
86
|
|
|
:param value: the input value |
87
|
|
|
:param expected_answer: the expected answer |
88
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_square` returns the wrong type |
89
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_square` returns the wrong value |
90
|
|
|
""" |
91
|
|
|
|
92
|
|
|
computed_answer = is_square(value) |
93
|
|
|
assert isinstance(computed_answer, is_square.__annotations__["return"]), "wrong type" |
94
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
95
|
|
|
|
96
|
|
|
|
97
|
|
|
def test_is_square_bad_n_type_str(): |
98
|
|
|
""" Test that :func:`lib.numbertheory.is_square` raises a ``TypeError`` for a non-``int`` value for `n` (``str``) |
|
|
|
|
99
|
|
|
""" |
100
|
|
|
with pytest.raises(TypeError): |
101
|
|
|
is_square("123") |
102
|
|
|
|
103
|
|
|
|
104
|
|
|
def test_is_square_bad_n_type_float(): |
105
|
|
|
""" Test that :func:`lib.numbertheory.is_square` raises a ``TypeError`` for a non-``int`` value for `n` (``float``) |
|
|
|
|
106
|
|
|
""" |
107
|
|
|
with pytest.raises(TypeError): |
108
|
|
|
is_square(123.0) |
109
|
|
|
|
110
|
|
|
|
111
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(1, 1), (17, 2), (10, 4), (30, 8), (275, 6), (10000, 25)]) |
|
|
|
|
112
|
|
|
def test_divisor_count_correctness(value: int, expected_answer: bool): |
113
|
|
|
""" Test the correctness of :func:`lib.numbertheory.divisor_count` using known answer tests |
114
|
|
|
|
115
|
|
|
:param value: the input value |
116
|
|
|
:param expected_answer: the expected answer |
117
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisor_count` returns the wrong type |
118
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisor_count` returns the wrong value |
119
|
|
|
""" |
120
|
|
|
|
121
|
|
|
computed_answer = divisor_count(value) |
122
|
|
|
assert isinstance(computed_answer, divisor_count.__annotations__["return"]), "wrong type" |
123
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
124
|
|
|
|
125
|
|
|
|
126
|
|
|
def test_divisor_count_bad_n_type_str(): |
|
|
|
|
127
|
|
|
""" Test that :func:`lib.numbertheory.divisor_count` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
128
|
|
|
(``str``) |
129
|
|
|
""" |
130
|
|
|
with pytest.raises(TypeError): |
131
|
|
|
divisor_count("123") |
132
|
|
|
|
133
|
|
|
|
134
|
|
|
def test_divisor_count_bad_n_type_float(): |
|
|
|
|
135
|
|
|
""" Test that :func:`lib.numbertheory.divisor_count` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
136
|
|
|
(``float``) |
137
|
|
|
""" |
138
|
|
|
with pytest.raises(TypeError): |
139
|
|
|
divisor_count(123.0) |
140
|
|
|
|
141
|
|
|
|
142
|
|
|
def test_divisor_count_bad_n_zero(): |
143
|
|
|
""" Test that :func:`lib.numbertheory.divisor_count` raises a ``ValueError`` for a non-positive value for `n` """ |
|
|
|
|
144
|
|
|
with pytest.raises(ValueError): |
145
|
|
|
divisor_count(0) |
146
|
|
|
|
147
|
|
|
|
148
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(1, 1), (17, 18), (10, 18), (30, 72), (275, 372), (10000, 24211)]) |
|
|
|
|
149
|
|
|
def test_divisor_sum_correctness(value: int, expected_answer: bool): |
150
|
|
|
""" Test the correctness of :func:`lib.numbertheory.divisor_sum` using known answer tests |
151
|
|
|
|
152
|
|
|
:param value: the input value |
153
|
|
|
:param expected_answer: the expected answer |
154
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisor_sum` returns the wrong type |
155
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisor_sum` returns the wrong value |
156
|
|
|
""" |
157
|
|
|
|
158
|
|
|
computed_answer = divisor_sum(value) |
159
|
|
|
assert isinstance(computed_answer, divisor_sum.__annotations__["return"]), "wrong type" |
160
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
161
|
|
|
|
162
|
|
|
|
163
|
|
|
def test_divisor_sum_bad_n_type_str(): |
164
|
|
|
""" Test that :func:`lib.numbertheory.divisor_sum` raises a ``TypeError`` for a non-``int`` value for `n` (``str``) |
|
|
|
|
165
|
|
|
""" |
166
|
|
|
with pytest.raises(TypeError): |
167
|
|
|
divisor_sum("123") |
168
|
|
|
|
169
|
|
|
|
170
|
|
|
def test_divisor_sum_bad_n_type_float(): |
|
|
|
|
171
|
|
|
""" Test that :func:`lib.numbertheory.divisor_sum` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
172
|
|
|
(``float``) |
173
|
|
|
""" |
174
|
|
|
with pytest.raises(TypeError): |
175
|
|
|
divisor_sum(123.0) |
176
|
|
|
|
177
|
|
|
|
178
|
|
|
def test_divisor_sum_bad_n_zero(): |
179
|
|
|
""" Test that :func:`lib.numbertheory.divisor_sum` raises a ``ValueError`` for a non-positive value for `n` """ |
|
|
|
|
180
|
|
|
with pytest.raises(ValueError): |
181
|
|
|
divisor_sum(0) |
182
|
|
|
|
183
|
|
|
|
184
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(1, 0), (17, 1), (10, 8), (30, 42), (275, 97), (10000, 14211)]) |
|
|
|
|
185
|
|
|
def test_divisor_sum_aliquot_correctness(value: int, expected_answer: bool): |
|
|
|
|
186
|
|
|
""" Test the correctness of :func:`lib.numbertheory.divisor_sum_aliquot` using known answer tests |
|
|
|
|
187
|
|
|
|
188
|
|
|
:param value: the input value |
189
|
|
|
:param expected_answer: the expected answer |
190
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisor_sum_aliquot` returns the wrong type |
191
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisor_sum_aliquot` returns the wrong value |
192
|
|
|
""" |
193
|
|
|
|
194
|
|
|
computed_answer = divisor_sum_aliquot(value) |
195
|
|
|
assert isinstance(computed_answer, divisor_sum_aliquot.__annotations__["return"]), "wrong type" |
196
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
197
|
|
|
|
198
|
|
|
|
199
|
|
|
def test_divisor_sum_aliquot_bad_n_type_str(): |
|
|
|
|
200
|
|
|
""" Test that :func:`lib.numbertheory.divisor_sum_aliquot` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
201
|
|
|
(``str``) |
202
|
|
|
""" |
203
|
|
|
with pytest.raises(TypeError): |
204
|
|
|
divisor_sum_aliquot("123") |
205
|
|
|
|
206
|
|
|
|
207
|
|
|
def test_divisor_sum_aliquot_bad_n_type_float(): |
|
|
|
|
208
|
|
|
""" Test that :func:`lib.numbertheory.divisor_sum_aliquot` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
209
|
|
|
(``float``) |
210
|
|
|
""" |
211
|
|
|
with pytest.raises(TypeError): |
212
|
|
|
divisor_sum_aliquot(123.0) |
213
|
|
|
|
214
|
|
|
|
215
|
|
|
def test_divisor_sum_aliquot_bad_n_zero(): |
|
|
|
|
216
|
|
|
""" Test that :func:`lib.numbertheory.divisor_sum_aliquot` raises a ``ValueError`` for a non-positive value for `n` |
|
|
|
|
217
|
|
|
""" |
218
|
|
|
with pytest.raises(ValueError): |
219
|
|
|
divisor_sum_aliquot(0) |
220
|
|
|
|
221
|
|
|
|
222
|
|
|
def test_is_probably_prime_correctness(): |
|
|
|
|
223
|
|
|
""" Test the correctness of :func:`lib.numbertheory.is_probably_prime` |
224
|
|
|
|
225
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_probably_prime` returns the wrong type |
226
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.is_probably_prime` returns the wrong value |
227
|
|
|
""" |
228
|
|
|
|
229
|
|
|
primes = load_dataset("general", "primes", data_type=int) |
230
|
|
|
primes = set(primes) |
231
|
|
|
upper_limit = 1000 # artificial cap to limit the run-time of this test |
232
|
|
|
max_prime = min(upper_limit, max(primes)) |
233
|
|
|
for n in range(1, max_prime + 1): |
|
|
|
|
234
|
|
|
computed_answer = is_probably_prime(n, k=5) |
235
|
|
|
assert isinstance(computed_answer, is_probably_prime.__annotations__["return"]), "wrong type" |
|
|
|
|
236
|
|
|
assert (n in primes) == computed_answer, "wrong answer" |
237
|
|
|
|
238
|
|
|
|
239
|
|
|
def test_is_probably_prime_bad_n_type_str(): |
|
|
|
|
240
|
|
|
""" Test that :func:`lib.numbertheory.is_probably_prime` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
241
|
|
|
(``str``) |
242
|
|
|
""" |
243
|
|
|
with pytest.raises(TypeError): |
244
|
|
|
is_probably_prime("2") |
245
|
|
|
|
246
|
|
|
|
247
|
|
|
def test_is_probably_prime_bad_n_type_float(): |
|
|
|
|
248
|
|
|
""" Test that :func:`lib.numbertheory.is_probably_prime` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
249
|
|
|
(``float``) |
250
|
|
|
""" |
251
|
|
|
with pytest.raises(TypeError): |
252
|
|
|
is_probably_prime(2.4) |
253
|
|
|
|
254
|
|
|
|
255
|
|
|
def test_miller_rabin_bad_n_type_str(): |
|
|
|
|
256
|
|
|
""" Test that :func:`lib.numbertheory.miller_rabin` raises a ``TypeError`` for a non-``int`` value for `n` (``str``) |
|
|
|
|
257
|
|
|
""" |
258
|
|
|
with pytest.raises(TypeError): |
259
|
|
|
miller_rabin("2") |
260
|
|
|
|
261
|
|
|
|
262
|
|
|
def test_miller_rabin_bad_n_type_float(): |
|
|
|
|
263
|
|
|
""" Test that :func:`lib.numbertheory.miller_rabin` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
264
|
|
|
(``float``) |
265
|
|
|
""" |
266
|
|
|
with pytest.raises(TypeError): |
267
|
|
|
miller_rabin(2.4) |
268
|
|
|
|
269
|
|
|
|
270
|
|
|
def test_miller_rabin_bad_n_too_small(): |
|
|
|
|
271
|
|
|
""" Test that :func:`lib.numbertheory.miller_rabin` raises a ``ValueError`` for too small a value for `n` """ |
|
|
|
|
272
|
|
|
with pytest.raises(ValueError): |
273
|
|
|
miller_rabin(2) |
274
|
|
|
|
275
|
|
|
|
276
|
|
|
def test_is_probably_prime_bad_k_type_str(): |
|
|
|
|
277
|
|
|
""" Test that :func:`lib.numbertheory.is_probably_prime` raises a ``TypeError`` for a non-``int`` value for `k` |
|
|
|
|
278
|
|
|
(``str``) |
279
|
|
|
""" |
280
|
|
|
with pytest.raises(TypeError): |
281
|
|
|
is_probably_prime(2, "14") |
282
|
|
|
|
283
|
|
|
|
284
|
|
|
def test_is_probably_prime_bad_k_type_float(): |
|
|
|
|
285
|
|
|
""" Test that :func:`lib.numbertheory.is_probably_prime` raises a ``TypeError`` for a non-``int`` value for `k` |
|
|
|
|
286
|
|
|
(``float``) |
287
|
|
|
""" |
288
|
|
|
with pytest.raises(TypeError): |
289
|
|
|
is_probably_prime(2, 12.3) |
290
|
|
|
|
291
|
|
|
|
292
|
|
|
def test_miller_rabin_bad_k_type_str(): |
|
|
|
|
293
|
|
|
""" Test that :func:`lib.numbertheory.miller_rabin` raises a ``TypeError`` for a non-``int`` value for `k` (``str``) |
|
|
|
|
294
|
|
|
""" |
295
|
|
|
with pytest.raises(TypeError): |
296
|
|
|
miller_rabin(2, "14") |
297
|
|
|
|
298
|
|
|
|
299
|
|
|
def test_miller_rabin_bad_k_type_float(): |
|
|
|
|
300
|
|
|
""" Test that :func:`lib.numbertheory.miller_rabin` raises a ``TypeError`` for a non-``int`` value for `k` |
|
|
|
|
301
|
|
|
(``float``) |
302
|
|
|
""" |
303
|
|
|
with pytest.raises(TypeError): |
304
|
|
|
miller_rabin(2, 12.3) |
305
|
|
|
|
306
|
|
|
|
307
|
|
|
def test_miller_rabin_bad_k_zero(): |
308
|
|
|
""" Test that :func:`lib.numbertheory.miller_rabin` raises a ``ValueError`` for :math:`k=0` """ |
309
|
|
|
with pytest.raises(ValueError): |
310
|
|
|
miller_rabin(9, 0) |
311
|
|
|
|
312
|
|
|
|
313
|
|
|
@pytest.mark.parametrize("siever", [prime_sieve, eratosthenes, segmented_eratosthenes]) |
314
|
|
|
def test_prime_sieve_correctness(siever): |
315
|
|
|
""" Test the correctness of all prime sieves in :func:`lib.numbertheory` including: |
316
|
|
|
* :func:`lib.numbertheory.primality.prime_sieve` |
317
|
|
|
* :func:`lib.numbertheory.primality.eratosthenes` |
318
|
|
|
* :func:`lib.numbertheory.primality.segmented_eratosthenes` |
319
|
|
|
|
320
|
|
|
The integers yielded by these sieves are tested for primality, up to some moderate bound. |
321
|
|
|
|
322
|
|
|
:raises AssertionError: if ``siever(upper_bound)`` yields the wrong type |
323
|
|
|
:raises AssertionError: if ``siever(upper_bound)`` yields the wrong value |
324
|
|
|
""" |
325
|
|
|
|
326
|
|
|
for p in siever(upper_bound=100): |
|
|
|
|
327
|
|
|
computed_answer = is_probably_prime(p) |
328
|
|
|
# assert isinstance(computed_answer, prime_sieve.__annotations__["return"]), "wrong type" |
329
|
|
|
assert computed_answer is True, "wrong answer" |
330
|
|
|
|
331
|
|
|
|
332
|
|
|
@pytest.mark.parametrize("upper_bound", [100, 10 ** 5, 10 ** 8, 10 ** 10]) |
333
|
|
|
def test_prime_sieve_correctness_bound(upper_bound): |
|
|
|
|
334
|
|
|
""" Test the correctness of all prime sieves in :mod:`lib.numbertheory` including: |
335
|
|
|
* :func:`lib.numbertheory.primality.prime_sieve` |
336
|
|
|
* :func:`lib.numbertheory.primality.eratosthenes` |
337
|
|
|
* :func:`lib.numbertheory.primality.segmented_eratosthenes` |
338
|
|
|
|
339
|
|
|
The integers yielded by these sieves are tested for primality, up to some moderate bound. The parameter |
|
|
|
|
340
|
|
|
`upper_bound` is set to various values to ensure all sieves are utilised. |
341
|
|
|
|
342
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.prime_sieve` yields the wrong type |
343
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.prime_sieve` yields the wrong value |
344
|
|
|
""" |
345
|
|
|
|
346
|
|
|
for p in takewhile(lambda _p: _p <= 100, prime_sieve(upper_bound)): |
|
|
|
|
347
|
|
|
computed_answer = is_probably_prime(p) |
348
|
|
|
# assert isinstance(computed_answer, prime_sieve.__annotations__["return"]), "wrong type" |
349
|
|
|
assert computed_answer is True, "wrong answer" |
350
|
|
|
|
351
|
|
|
|
352
|
|
|
def test_prime_sieve_bad_upper_bound_type_str(): |
|
|
|
|
353
|
|
|
""" Test that :func:`lib.numbertheory.prime_sieve` raises a ``TypeError`` for a non-``int`` value for `upper_bound` |
|
|
|
|
354
|
|
|
(``str``) |
355
|
|
|
""" |
356
|
|
|
with pytest.raises(TypeError): |
357
|
|
|
prime_sieve("123") |
358
|
|
|
|
359
|
|
|
|
360
|
|
|
def test_prime_sieve_bad_upper_bound_type_float(): |
|
|
|
|
361
|
|
|
""" Test that :func:`lib.numbertheory.prime_sieve` raises a ``TypeError`` for a non-``int`` value for `upper_bound` |
|
|
|
|
362
|
|
|
(``float``) |
363
|
|
|
""" |
364
|
|
|
with pytest.raises(TypeError): |
365
|
|
|
prime_sieve(12.3) |
366
|
|
|
|
367
|
|
|
|
368
|
|
|
def test_prime_sieve_bad_upper_bound_negative(): |
|
|
|
|
369
|
|
|
""" Test that :func:`lib.numbertheory.prime_sieve` raises a ``ValueError`` for :math:`upper\\_bound \\lt 0` """ |
|
|
|
|
370
|
|
|
with pytest.raises(ValueError): |
371
|
|
|
prime_sieve(-14) |
372
|
|
|
|
373
|
|
|
|
374
|
|
|
def test_prime_sieve_bad_upper_bound_too_big(): |
|
|
|
|
375
|
|
|
""" Test that :func:`lib.numbertheory.prime_sieve` raises a ``ValueError`` for |
|
|
|
|
376
|
|
|
:math:`\\mbox{upper_bound} \ge 10^{16}` |
377
|
|
|
""" |
378
|
|
|
too_big = 10 ** 20 |
379
|
|
|
with pytest.raises(ValueError): |
380
|
|
|
prime_sieve(upper_bound=too_big) |
381
|
|
|
|
382
|
|
|
|
383
|
|
|
def test_divisors_sieve_correctness_proper(): |
|
|
|
|
384
|
|
|
""" Test the correctness of the divisors prime sieve :func:`lib.numbertheory.divisors_sieve` |
385
|
|
|
|
386
|
|
|
The divisors yielded by this sieve are tested to ensure that they do divide the given integer :math:`n`, up to some |
|
|
|
|
387
|
|
|
moderate bound on :math:`n`. Additionally, it is checked that :math:`1` is included as a proper divisor of |
|
|
|
|
388
|
|
|
:math:`n` and that :math:`n` is **not**. |
389
|
|
|
|
390
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisors_sieve` yields the wrong type |
391
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisors_sieve` yields the wrong value |
392
|
|
|
""" |
393
|
|
|
|
394
|
|
|
for n, divisors in enumerate(divisors_sieve(100, proper=True)): |
|
|
|
|
395
|
|
|
for divisor in divisors: |
396
|
|
|
# assert isinstance(divisor, divisors_sieve.__annotations__["return"]), "wrong type" |
397
|
|
|
assert (n + 1) % divisor == 0, "non-divisor included by divisors_sieve" |
398
|
|
|
assert 1 in divisors, "wrong answer: 1 divides everything" |
399
|
|
|
if n + 1 > 1: |
400
|
|
|
assert n + 1 not in divisors, "wrong answer: n is not a proper divisor of itself" |
401
|
|
|
|
402
|
|
|
|
403
|
|
|
def test_divisors_sieve_correctness_not_proper(): |
|
|
|
|
404
|
|
|
""" Test the correctness of the divisors prime sieve :func:`lib.numbertheory.divisors_sieve` |
405
|
|
|
|
406
|
|
|
The divisors yielded by this sieve are tested to ensure that they do divide the given integer :math:`n`, up to some |
|
|
|
|
407
|
|
|
moderate bound on :math:`n`. Additionally, it is checked that :math:`1` is included as a divisor of along with |
|
|
|
|
408
|
|
|
:math:`n` itself. |
409
|
|
|
|
410
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisors_sieve` yields the wrong type |
411
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisors_sieve` yields the wrong value |
412
|
|
|
""" |
413
|
|
|
|
414
|
|
|
for n, divisors in enumerate(divisors_sieve(100, proper=False)): |
|
|
|
|
415
|
|
|
for divisor in divisors: |
416
|
|
|
# assert isinstance(divisor, divisors_sieve.__annotations__["return"]), "wrong type" |
417
|
|
|
assert (n + 1) % divisor == 0, "non-divisor included by divisors_sieve" |
418
|
|
|
assert 1 in divisors, "wrong answer: 1 divides everything" |
419
|
|
|
assert n + 1 in divisors, "wrong answer: n is a divisor of itself" |
420
|
|
|
|
421
|
|
|
|
422
|
|
|
@pytest.mark.parametrize("upper_bound,proper,aggregate,expected_answer", |
423
|
|
|
[(8, True, None, [{1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}]), |
424
|
|
|
(7, False, None, [{1}, {1, 2}, {1, 3}, {1, 2, 4}, {1, 5}, {1, 2, 3, 6}, {1, 7}]), |
|
|
|
|
425
|
|
|
(12, True, "count", [1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 5]), |
426
|
|
|
(12, False, "count", [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6]), |
427
|
|
|
(10, True, "sum", [1, 1, 1, 3, 1, 6, 1, 7, 4, 8]), |
428
|
|
|
(10, False, "sum", [1, 3, 4, 7, 6, 12, 8, 15, 13, 18])]) |
429
|
|
|
def test_divisors_sieve_correctness(upper_bound: int, proper: bool, aggregate: Optional[str], |
430
|
|
|
expected_answer: Union[set, int]): |
|
|
|
|
431
|
|
|
""" Test the correctness of :func:`lib.numbertheory.divisors_sieve` using known answer tests |
432
|
|
|
|
433
|
|
|
:param upper_bound: the upper bound of the sieve |
434
|
|
|
:param proper: whether to consider just proper divisors or not |
435
|
|
|
:param aggregate: the aggregation function to apply |
436
|
|
|
:param expected_answer: the expected answer |
437
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisors_sieve` returns the wrong type |
438
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.divisors_sieve` returns the wrong value |
439
|
|
|
""" |
440
|
|
|
|
441
|
|
|
sieve = divisors_sieve(upper_bound=upper_bound, proper=proper, aggregate=aggregate) |
442
|
|
|
computed_answer = list(sieve) |
443
|
|
|
# assert isinstance(computed_answer, divisors_sieve.__annotations__["return"]), "wrong type" |
444
|
|
|
assert computed_answer == expected_answer, "wrong answer" |
445
|
|
|
|
446
|
|
|
|
447
|
|
|
def test_divisors_sieve_bad_upper_bound_type_str(): |
|
|
|
|
448
|
|
|
""" Test that :func:`lib.numbertheory.divisors_sieve` raises a ``TypeError`` for a non-``int`` value for |
|
|
|
|
449
|
|
|
`upper_bound` (``str``) |
450
|
|
|
""" |
451
|
|
|
with pytest.raises(TypeError): |
452
|
|
|
divisors_sieve("123", proper=True) |
453
|
|
|
|
454
|
|
|
|
455
|
|
|
def test_divisors_sieve_bad_upper_bound_type_float(): |
|
|
|
|
456
|
|
|
""" Test that :func:`lib.numbertheory.divisors_sieve` raises a ``TypeError`` for a non-``int`` value for |
|
|
|
|
457
|
|
|
`upper_bound` (``float``) |
458
|
|
|
""" |
459
|
|
|
with pytest.raises(TypeError): |
460
|
|
|
divisors_sieve(12.3, proper=False) |
461
|
|
|
|
462
|
|
|
|
463
|
|
|
def test_divisors_sieve_bad_upper_bound_negative(): |
|
|
|
|
464
|
|
|
""" Test that :func:`lib.numbertheory.divisors_sieve` raises a ``ValueError`` for :math:`\\mbox{upper_bound} \\lt 0` |
|
|
|
|
465
|
|
|
""" |
466
|
|
|
with pytest.raises(ValueError): |
467
|
|
|
divisors_sieve(-14, proper=True) |
468
|
|
|
|
469
|
|
|
|
470
|
|
|
def test_divisors_sieve_bad_aggregate_type_float(): |
|
|
|
|
471
|
|
|
""" Test that :func:`lib.numbertheory.divisors_sieve` raises a ``TypeError`` for a non-``str`` value for `aggregate` |
|
|
|
|
472
|
|
|
(``float``) |
473
|
|
|
""" |
474
|
|
|
with pytest.raises(TypeError): |
475
|
|
|
divisors_sieve(10, proper=False, aggregate=3.14) |
476
|
|
|
|
477
|
|
|
|
478
|
|
|
def test_divisors_sieve_bad_aggregate_invalid(): |
|
|
|
|
479
|
|
|
""" Test that :func:`lib.numbertheory.divisors_sieve` raises a ``ValueError`` for invalid value of `aggregate` """ |
|
|
|
|
480
|
|
|
with pytest.raises(ValueError): |
481
|
|
|
divisors_sieve(10, proper=True, aggregate="foo") |
482
|
|
|
|
483
|
|
|
|
484
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(0, {0: 1}), (1, {1: 1}), (16, {2: 4})]) |
485
|
|
|
def test_factor_correctness(value, expected_answer): |
486
|
|
|
""" Test the correctness of :func:`lib.numbertheory.factor` with known-answer-tests |
487
|
|
|
|
488
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` returns the wrong type |
489
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` returns the wrong value |
490
|
|
|
""" |
491
|
|
|
|
492
|
|
|
computed_value = factor(value) |
493
|
|
|
# assert isinstance(computed_value, factor.__annotations__["return"]), "wrong type" |
494
|
|
|
assert computed_value == expected_answer, "wrong value" |
495
|
|
|
|
496
|
|
|
|
497
|
|
|
@pytest.mark.parametrize("value,expected_answer", [(16, {2: 4}), (35, {5: 1, 7: 1}), (1001, {7: 1, 11: 1, 13: 1})]) |
|
|
|
|
498
|
|
|
def test_factor_correctness_negative(value, expected_answer): |
|
|
|
|
499
|
|
|
""" Test the correctness of :func:`lib.numbertheory.factor` with known-answer-tests |
500
|
|
|
|
501
|
|
|
Each `value` is factored. This factorisation is combined with a factor of :math:`-1` to give the expected |
|
|
|
|
502
|
|
|
factorisation of :math:`-value`. This negative value is then factored, and the two results are checked for equality. |
|
|
|
|
503
|
|
|
|
504
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` returns the wrong type |
505
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` returns the wrong value |
506
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` doesn't include a factor of :math:`-1` |
|
|
|
|
507
|
|
|
""" |
508
|
|
|
|
509
|
|
|
computed_value = factor(value) |
510
|
|
|
# assert isinstance(computed_value, factor.__annotations__["return"]), "wrong type" |
511
|
|
|
assert computed_value == expected_answer, "wrong value" |
512
|
|
|
computed_value_negative = factor(-1 * value) |
513
|
|
|
# assert isinstance(computed_value_negative, factor.__annotations__["return"]), "wrong type" |
514
|
|
|
assert -1 not in computed_value.keys(), "missing factor of -1" |
515
|
|
|
computed_value[-1] = 1 |
516
|
|
|
assert computed_value == computed_value_negative, "wrong value" |
517
|
|
|
|
518
|
|
|
|
519
|
|
|
def test_factor_correctness_random(): |
520
|
|
|
""" Test the correctness of :func:`lib.numbertheory.factor` with known-answer-tests |
521
|
|
|
|
522
|
|
|
A random integer is built as a product of several small primes (selected with replacement); this random integer has |
|
|
|
|
523
|
|
|
a known factorisation. :func:`lib.numbertheory.factor` is used to factor the constructed number and it is compared |
|
|
|
|
524
|
|
|
to the known and expected factorisation. |
525
|
|
|
|
526
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` returns the wrong type |
527
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.factor` returns the wrong value |
528
|
|
|
""" |
529
|
|
|
|
530
|
|
|
# First, build a random integer as a product of several small primes (selected with replacement) |
531
|
|
|
primes = load_dataset("general", "primes", data_type=int) |
532
|
|
|
value, factorisation = 1, Counter() |
533
|
|
|
while value < 10 ** 6: |
534
|
|
|
p = choice(primes) |
|
|
|
|
535
|
|
|
value *= p |
536
|
|
|
factorisation[p] += 1 |
537
|
|
|
factorisation = dict(factorisation) |
538
|
|
|
|
539
|
|
|
# Factor the constructed integer and check that it matches the construction |
540
|
|
|
computed_value = factor(value) |
541
|
|
|
# assert isinstance(computed_value_negative, factor.__annotations__["return"]), "wrong type" |
542
|
|
|
assert computed_value == factorisation, "wrong value" |
543
|
|
|
|
544
|
|
|
|
545
|
|
|
def test_factor_bad_n_type_str(): |
546
|
|
|
""" Test that :func:`lib.numbertheory.factor` raises a ``TypeError`` for a non-``int`` value for `n` (``str``) """ |
|
|
|
|
547
|
|
|
with pytest.raises(TypeError): |
548
|
|
|
factor("123") |
549
|
|
|
|
550
|
|
|
|
551
|
|
|
def test_factor_bad_n_type_float(): |
552
|
|
|
""" Test that :func:`lib.numbertheory.factor` raises a ``TypeError`` for a non-``int`` value for `n` (``float``) """ |
|
|
|
|
553
|
|
|
with pytest.raises(TypeError): |
554
|
|
|
factor(145.678) |
555
|
|
|
|
556
|
|
|
|
557
|
|
|
@pytest.mark.parametrize("square_free", [6, 35, 77]) |
558
|
|
|
def test_perfect_power_exponent_correctness_square_free(square_free): |
|
|
|
|
559
|
|
|
""" Test the correctness of :func:`lib.numbertheory.perfect_power_exponent` for square-free inputs |
|
|
|
|
560
|
|
|
|
561
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.perfect_power_exponent` returns the wrong type |
|
|
|
|
562
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.perfect_power_exponent` returns the wrong value |
|
|
|
|
563
|
|
|
""" |
564
|
|
|
|
565
|
|
|
computed_value = perfect_power_exponent(square_free) |
566
|
|
|
assert isinstance(computed_value, perfect_power_exponent.__annotations__["return"]), "wrong type" |
|
|
|
|
567
|
|
|
assert computed_value == 1, "wrong value" |
568
|
|
|
|
569
|
|
|
|
570
|
|
|
@pytest.mark.parametrize("square_free", [6, 35, 77]) |
571
|
|
|
def test_perfect_power_exponent_correctness_not_square_free(square_free): |
|
|
|
|
572
|
|
|
""" Test the correctness of :func:`lib.numbertheory.perfect_power_exponent` for **non** square-free inputs |
|
|
|
|
573
|
|
|
|
574
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.perfect_power_exponent` returns the wrong type |
|
|
|
|
575
|
|
|
:raises AssertionError: if :func:`lib.numbertheory.perfect_power_exponent` returns the wrong value |
|
|
|
|
576
|
|
|
""" |
577
|
|
|
|
578
|
|
|
exponent = randint(2, 10) # force each square-free number to be a perfect power |
579
|
|
|
computed_value = perfect_power_exponent(square_free ** exponent) |
580
|
|
|
assert isinstance(computed_value, perfect_power_exponent.__annotations__["return"]), "wrong type" |
|
|
|
|
581
|
|
|
assert computed_value == exponent, "wrong value" |
582
|
|
|
|
583
|
|
|
|
584
|
|
|
def test_perfect_power_exponent_bad_n_type_str(): |
|
|
|
|
585
|
|
|
""" Test that :func:`lib.numbertheory.perfect_power_exponent` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
586
|
|
|
(``str``) |
587
|
|
|
""" |
588
|
|
|
with pytest.raises(TypeError): |
589
|
|
|
perfect_power_exponent("123") |
590
|
|
|
|
591
|
|
|
|
592
|
|
|
def test_perfect_power_exponent_bad_n_type_float(): |
|
|
|
|
593
|
|
|
""" Test that :func:`lib.numbertheory.perfect_power_exponent` raises a ``TypeError`` for a non-``int`` value for `n` |
|
|
|
|
594
|
|
|
(``float``) |
595
|
|
|
""" |
596
|
|
|
with pytest.raises(TypeError): |
597
|
|
|
perfect_power_exponent(145.678) |
598
|
|
|
|
599
|
|
|
|
600
|
|
|
def test_perfect_power_exponent_bad_n_zero(): |
|
|
|
|
601
|
|
|
""" Test that :func:`lib.numbertheory.perfect_power_exponent` raises a ``ValueError`` for :math:`n=0` """ |
|
|
|
|
602
|
|
|
with pytest.raises(ValueError): |
603
|
|
|
perfect_power_exponent(0) |
604
|
|
|
|