Talk:Carmichael 3 strong pseudoprimes: Difference between revisions
Talk:Carmichael 3 strong pseudoprimes (view source)
Revision as of 12:57, 17 November 2017
, 6 years agoUndo revision 256051 by Dinosaur (talk) see https://www.wordhippo.com/what-is/the-plural-of/division.html "In more general, commonly used, contexts, the plural form will also be division"
(Undo revision 256051 by Dinosaur (talk) see https://www.wordhippo.com/what-is/the-plural-of/division.html "In more general, commonly used, contexts, the plural form will also be division") |
|||
| (6 intermediate revisions by 2 users not shown) | |||
Line 1:
==Integer arithmetic==
Integer arithmetic can be a delicate matter, not just because of overflows. With division, sometimes the formula will never produce a remainder, as in n(n + 1)/2, and sometimes the divisor is always a factor for more complex reasons - as with <code>(P1 - 1)*(H3 + P1)/D</code>. But if a term produces a fractional part, is it to be discarded or not? Some languages (such as Pascal) insist on "div" instead of "/" so that one thinks about truncating division, others (such as pl/i) just generate the fractional part and proceed: perhaps the result will round? truncate? to the desired value, or perhaps other terms will cancel out the fractional parts and all will be well, or, perhaps they will combine and the result will be out by one, ''etc''. And some formulae require the fractional parts, as in the expression for the n'th Fibonacci number where each term generates an ''infinite'' non-repeating fractional part, and, they cancel ''exactly'', even for large values of n... In source code,
:<code>(((1 + SQRT(5))/2)**N - ((1 - SQRT(5))/2)**N)/SQRT(5)</code>
or, in mathematical notation (possibly not rendered),
:<math>\frac{1}{\sqrt{5}}\left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right]</math>
::All the division in this task should result in an integer value. So the best solution is probably to throw/raise an exception if it doesn't.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:29, 24 October 2017 (UTC)
==What model MOD is your MOD?==
Directly translating the given formulae involves a trap. There is an expression ''-Prime1 squared mod h3'', and translating this to <code>MOD(-P1**2,H3)</code> may not work. The behaviour of the MOD function for negative numbers varies between language, compiler, and cpu. For positive numbers there is no confusion. However, in some cases one wants an affine shift as in day-of-the-week calculations from a daynumber, D: given MOD(D,7), one wants the same result with MOD(D - 7,7) or any other such shift and indeed, this happens with some versions of MOD. But not all, as Prof. Knuth remarks in his description of the calculation of the date for Easter. The MOD function can also work as follows:
<pre>
D -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
MOD(D,3) -1 0 -2 -1 0 -2 -1 0 1 2 0 1 2 0 1
MOD(3 + MOD(D,3),3) 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
</pre>
Thus, <code>MOD(-1,3) + MOD(4,3) = -1 + 1</code> and <code>MOD(3,3) = 0</code> so that ''(a + b) mod n'' does come out as ''[(a mod n) + (b mod n)] mod n'' as is expected, but in a different way: (-1 ''mod'' 3) + (4 ''mod'' 3) = 2 + 1, thus the need for the second ''mod''. So, MOD and ''mod'' are different. However, this MOD is consistent with integer division that truncates. If ''q·f = n/d'' where q is the integer part and f the fractional part of the division, then the remainder is ''fd'' and has a sign too. Another computer/compiler/language version of MOD may not differ from ''mod''.
Here I am supposing that ''(h3+Prime1)*(Prime1-1) mod d == 0 and -Prime1 squared mod h3 == d mod h3'' is evaluated as ''{[(h3 + Prime1)*(Prime1 - 1) mod d] == 0} and {[-(Prime1 squared) mod h3] == d mod h3}'' which is to say it is ''[-(Prime1 squared)] mod h3'' not ''-[(Prime1 squared) mod h3]'' where the first case involves the MOD(negative number) while the second is -MOD(positive number) and the only way that result could match ''d mod h3'' is when both are zero.
Testing with the peculiar sign ignored via <code>.AND. (MOD(P1**2,H3) .EQ. MOD(D,H3))) THEN</code> gives limited results:
<pre>
Carmichael numbers that are the product of three primes:
P1 x P2 x P3 = C
3 11 17 561
5 29 73 10585
7 19 67 8911
13 61 397 314821
13 37 241 115921
19 43 409 334153
31 991 15361 471905281
37 109 2017 8134561
41 1721 35281 2489462641
43 631 13567 368113411
43 271 5827 67902031
43 127 2731 14913991
61 421 12841 329769721
61 181 5521 60957361</pre>
Which turns out to be when the two terms have remainders of one.
:-p squared means -p*p. -p**2 or -p^2 may depend on the language's operator precedence. Use brackets if in doubt. mod of a negative numbers have caused me more problems than I anticipated. We have discussed them on another task to which I would link if I could find it. We concluded that C defined it as a remainder function and many languages have followed suit. It is used here to mean the mathematical modulus function. I think this is another solution to the solutions suggested somewhere else on RC. I promise than any further task using mod of a negative number will include a health warning!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 11:51, 23 October 2017 (UTC)
==Formula in Fortran contribution invisible to most browsers==
In the Fortran contribution (now moved to the ''Discussion'', above), there is a formula which is at present invisible to all but a minority type of browser. The majority browser type, which displays a graphic file for <math> tag formula rather than generating text from locally installed fonts and local MathML processing, shows only a white space after the phrase: '''as in the expression for the n'th Fibonacci number:'''.
To see and test any fixes the problem, view the page in a mainstream browser like Chrome, Safari, or IE/Edge (rather than in one of the minority browsers like Firefox, which, when requisite fonts are installed, uses local MathML processing. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:32, 24 September 2016 (UTC)
| |||