Printable View
Blaise Pascal invent a rule how to check if number divides on another number.
I don't know exactly how it sounds but from school I remember that if sum of digits in given number divides on three, then this number is divides on three.
Also there exist a rules of division on 7, 11 etc.
Can this help us somehow?
I mean make sum of 10000000 and divide it on 3 takes few seconds, not few days, right?
(edited because what was intended as succinctness read like approbation)
SoB is always looking for ways to speed up the search. Some large improvements in sieving speed happened in part because of discussions on these boards. However, the existing speed improvements have already taken us beyond where this particular idea would be helpful. There are two major reasons why we have already outrun this idea:
Firstly, sieving is about checking whether the numbers are divisible by "small" primes, and that process is already far past the stage where anybody has simple rules.
Secondly, modular arithmetic gives us a way to determine the remainder after division that is much faster than creating the whole number. When the remainder is zero, the number is a divisor.
So no, these rules have additional insight for SoB.
thanks for explanation
but division on three is a part oа whole rule
http://ru.wikipedia.org/wiki/%D0%9F%...B0%D0%BB%D1%8F
that's russian version, and alas no english variant
but you can look at math at least
I'll try to find it later.
Off-topic:I feel like I'm reading a book in a mirror when I look at Russian. Is there a written or spoken language that both languages are a descendant of? some of the letters seem similar.Quote:
Originally Posted by Death
you can bet that "A" looks and pronounces equal at both languages )))
I can't find english version
It should sounds like Pascal's Token or Pascal's Rule
but due to this damn programming language there's a lot of pages that have no common with Blaise Pascal ((
Okay I mean something like this -
http://en.wikipedia.org/wiki/Divisibility_rule
Divisor Divisibility Condition Examples
2 The last digit is even (0, 2, 4, 6, or 8). 1,294: 4 is even.
3 The sum of the digits is divisible by 3 . 405: 4 + 0 + 5 = 9, which clearly is divisible by 3.
4 The number obtained from these examples must be divisible by 4, as follows:
If the tens digit is even, the last digit is divisible by 4 (0, 4, 8). 168: 6 is even, and 8 is divisible by 4.
If the tens digit is odd, the last digit plus 2 is divisible by 4 (2, 6). 5,496: 9 is odd, and 6+2 is divisible by 4.
If the number formed by the last two digits is divisible by 4. 2,092: 92 is divisible by 4.
5 The last digit is 0 or 5. 490: the last digit is 0.
6 It is divisible by 2 and by 3. 24: it is divisible by 2 and by 3.
Sum the last digit with four times the sum of all other digits. 1020: (1 + 0 + 2) Ч 4 + 0 = 12
7 The number obtained from these examples must be divisible by 7, as follows:
Sum the digits in alternate blocks of three from right to left, then difference the two sums. 2,911,272: − (2 + 272) + 911 = 637
Sum the number with the last two digits removed, doubled, plus the last two digits. 364: (3x2) + 64 = 70.
Sum the number with the last digit removed with 5 times the last digit. 364: 36 + (5Ч4) = 56.
Subtract twice the last digit from the rest of the number. 364: 36 − (2Ч4) = 28.
8 The number obtained from these examples must be divisible by 8, as follows:
If the hundreds digit is even, examine the number formed by the last two digits. That number must be divisible by 4. 624: 24.
If the hundreds digit is odd, examine the number obtained by the last two digits plus 4. 352: 52+4 = 56.
Add the digits with the last digit removed, doubled, plus the last digit. 56: (5x2) + 6 = 16.
9 The sum of the digits must be divisible by 9 . 2,880: 2 + 8 + 8 + 0 = 18.
1 + 8 = 9.
10 The last digit is 0. 130: the last digit is 0.
11 The number obtained from these examples must be divisible be 11, as follows:
Add the digits in blocks of two from right to left. 627: 6 + 27 = 33.
Difference the number with the last digit removed with the last digit. 627: 62 - 7 = 55.
Add alternate digits, then difference the two sums. 182,919: − (1 + 2 + 1) + (8 + 9 + 9) = 22.
12 It is divisible by 3 and by 4. 324: it is divisible by 3 and by 4.
Subtract the number with the last digit removed, doubled, with the last digit. 324: (32x2) − 4 = 60.
13 The number obtained from these examples must be divisible by 13, as follows:
Add the digits in alternate blocks of three from right to left, then subtract the two sums. 2,911,272: − (2 + 272) + 911 = 637
Add the number with the last digit removed with 4 times the last digit. 338: 33 + (8Ч4) = 65.
Subtract the number with the last digit removed with 9 times the last digit. 637: 63 − (7Ч9) = 0.
14 It is divisible by 2 and by 7. 224: it is divisible by 2 and by 7.
Add the number with the last two digits removed, doubled, plus the last two digits. The answer must be divisible by 7. 364: (3x2) + 64 = 70.
15 It is divisible by 3 and by 5. 390: it is divisible by 3 and by 5.
16 The number obtained from these examples must be divisible by 16, as follows:
If the thousands digit is even, examine the number formed by the last three digits. 254,176: 176.
If the thousands digit is odd, examine the number formed by the last three digits plus 8. 3,408: 408+8 = 416.
Sum the number with the last two digits removed, times 4, plus the last two digits. 176: (1x4) + 76 = 80.
17 Subtract the number with the last two digits removed, doubled, with the last two digits. 187: − (1x2) + 87 = 85.
Alternatively subtract and add blocks of two digits from the end, doubling the last block and halving the result of the operation, rounding any decimal end result as necessary. 20,98,65: (65 - (98x2)) : 2 + 40 = - 25.5 = 255 = 15x17
Subtract the number with the last digit removed with 5 times the last digit. 85: − 8 + (5Ч5) = 17.
18 It is divisible by 2 and by 9. 342: it is divisible by 2 and by 9.
19 Add the number with the last digit removed with twice the last digit. 437: 43 + (7x2) = 57.
20 It is divisible by 10, and the tens digit is even. 360: is divisible by 10, and 6 is even.
If the number formed by the last two digits is divisible by 20. 480: 80 is divisible by 20.
wblipp explain me why this may be unuseful, but take a look!
You are providing us divisibility rules for factors <=49. We have sieved already beyond 400000000000000. H. :Pokes:
oh well if number divides on 5 we don't need to check whether it divides on 400000000000000, right?
Death,
Basically what people are telling you is that the methods that are currently in use are far superior to the ones that you are describing.
As an example instead of using the sieve client why don't we write out each number in the dat and look for ones that are even, then try three etc...
Now of course you are proposing something better than writing number out numbers by hand but it's still much worse than what we are currently using.
Try googleing factoring programs or looking at the mersenne forums. You will see that what you propose has been used and better methods have been developed.
okay, okay, this was just idea )))