has anyone ever noticed that if u add up the digits of any multiple of three, they always add up to a number that is a multiple of three? for example 21 = 2 + 1 = 3, 111 = 1 + 1 +1 = 3, or 63 = 6 + 3 = 9.

Have you noticed how nature adheres to Fibonacci?

has anyone ever noticed that if u add up the digits of any multiple of three, they always add up to a number that is a multiple of three? for example 21 = 2 + 1 = 3, 111 = 1 + 1 +1 = 3, or 63 = 6 + 3 = 9.

It's actually the way to check for divisability by 3 when looking for prime factors.

Yeah there's all kinds of tricks like this.

I like the 9 stuff more/

me too. they flip in the multiplication tables.

a + 10b + 100c + ... = 3k
(a + 10b + 100c + ...) - (a + b + c + ...) = 3k - (a + b + c + ...)
9b + 99c + ... = 3k - (a + b + c + ...)

3(3b + 33c + ... - k) = a + b + c + ...

So, 3 | (a + b + c + ..)

Sorry for the horrible (and lazy) notation.

Nice proof.

That's some fancy ciphering right there. I never knew that about multiples of 3...I guess 'cause my brain didn't come with a math co-processor.

That doesn't work in a field of characteristic 2.

;)

who remembers the trick for finding multiples of 7?

who remembers the trick for finding multiples of 7?

I didn't think there was a trick for 7.

The number 9 has the same trick as 3 though. The sum of the digits will always itself be evenly divisible by 9, if the underlying number is. For example, take 1,764, 1+7+6+4 = 18 which is evenly divisible by 9, thus so is 1,764 (and so is 7,614, or 6,147, or 4,761).

who remembers the trick for finding multiples of 7?

Work in octal :)

Those of you who have not thought about the 'multiple of three' rule maybe interested to read my explanation:

Decimal numbers have columns for units, tens, hundreds, thousands etc.

notice that:
1 mod 3 = 1
10 mod 3 = 1
100 mod 3 = 1
For each power of ten the remainder of a division by three is always one. So incrementing any digit in a base 10 number will increase the remainder of a divide-by-three by one. Hence, if the sum of each power of 10 is divisible by three then so will the whole number.

Work in octal :)Yes, Absane´s proof (post 7) can be generalized by letting B, the base, replace his 10. I.e. for your case, B=7.

I doubt if this helps speed the search for big primes much as the converison of candidate number, N, to many lesser prime bases must be slow, but I know very little about how to search for big primes.

Those of you who have not thought about the 'multiple of three' rule maybe interested to read my explanation:

Decimal numbers have columns for units, tens, hundreds, thousands etc.

notice that:
3 mod 1 = 1
3 mod 10 = 1
3 mod 100 = 1
For each power of ten the remainder of a division by three is always one. So incrementing any digit in a base 10 number will increase the remainder of a divide-by-three by one. Hence, if the sum of each power of 10 is divisible by three then so will the whole number.

Are you referring to modulus (% in C++)?
3 % 1 = 0
3 % 10 = 3
3 % 100 = 3

1 % 3 = 1
10 % 3 = 1
100 % 3 = 1

yes, you know what I mean :p

K, just checking. :)

Following the work of Absane :

a + 10b + 100c + ... = 7k
(a + 10b + 100c + ...) - (a + 3b + 30c + ...) = 7k - (a + 3b + 30c + ...)
7b + 70c + ... = 7k - (a + 3b + 30c + ...)

7(b - 10c - ... + k) = a + 3b + 30c + ...

So 7 | (a + 3b + 30c + ...)
Or 7 | a + 3(b + 10c + 100d + ...)

I haven't been able to make this work recursively, so this suffices for the time being.

lets see if 6594 is divisible by 7.
659*3 = 1977+4 = 1981
198*3 = 594+1 = 595
59*3 = 177+5 = 182
18*3 = 54+2 = 56
5*3 = 15 + 6 = 21
2*3 = 6 + 1 = 7

This needs 6 iterations of a thousands number just to arrive at 7.


It's probably much faster working with modular arithmetic, but I'll just stick with base-10.


Let's try another particular algorithm:

a + 10b + 100c + ... = 7k
(a + 10b + 100c + ...) - (a + 10b + 2c + 20d + 200e + ...) = 7k - (a + 10b + 2c + 20d + 200e + ...)
98c+ 980d + ... = 7k - (a + 10b + 2c + 20d + 200e + ...)

7(14c - 140d - ... + k) = a + 10b + 2c + 20d + 200e + ...

So 7 | (a + 10b + 2c + 20d + 200e + ...)
Or 7 | a + 10b + 2(c + 10d + 100e + ...)

example,
6594 :
65*2 = 130 + 94 = 224
2*2 = 4 + 24 = 28

So going one step further helps reduce the time considerably.

Since 7 can get variously close to the successive orders of 10, I can see that a general form of the algorithm is possible, because it resembles the .142857 cyclic pattern. Specifically, the left hand side of the equation becomes 7b + 98c + 994d + 9996e + 99995f + 999999g ... with the ellipses indicating the first repetition of the cycle.

Then one should obtain 7 | a + 3b + 2c + 6d + 4e + 5f + g + 3h + 2i + 6j + 4k + 5l + ... (I displayed two cycles), where a is the units, b the tens, etc.

example :
6594 6*6 + 2*5 + 3*9 + 4 = 36 + 10 + 27 + 6 = 77
77 is further dissolved into 3*7 + 7 = 28.
28 is 3*2 + 8 = 14
and finally 3*1 + 4 = 7.

This would be the 1-3-2-6-4-5 cycle.

i've just started to get interested in number theory, and have been noticing some interesting things. like the fact that the number 7 is the only number below 10 whose reciprical appears irrational at first glance, and is also equal to pi - 3 out to 2 decimal places. and if one takes 22 / 7 they get pi to 2 decimals places. the reciprical of 22 is .0454545.., 4 time 5 equals 20, which is nearly equal to e^pi - pi. :) oh yeah, e^pi - the natural logarithm of pi nearly equals 22.

I like the 11 multiplication trick.
Split and add.
Split the numbers, and put their sum in the middle...
11 * 43 = 473
11 8 32 = 352

I especially like it because no one taught it to me - I figured it out on my own when I was a kid.

I like the 11 multiplication trick.
Split and add.
Split the numbers, and put their sum in the middle...
11 * 43 = 473
11 8 32 = 352

I especially like it because no one taught it to me - I figured it out on my own when I was a kid.

nice find. :)

I like the 11 multiplication trick.
Split and add.
Split the numbers, and put their sum in the middle...
11 * 43 = 473
11 8 32 = 352

I especially like it because no one taught it to me - I figured it out on my own when I was a kid.I agree with devire, nice find :)

Since 7 can get variously close to the successive orders of 10, I can see that a general form of the algorithm is possible, because it resembles the .142857 cyclic pattern. Specifically, the left hand side of the equation becomes 7b + 98c + 994d + 9996e + 99995f + 999999g ... with the ellipses indicating the first repetition of the cycle.

Then one should obtain 7 | a + 3b + 2c + 6d + 4e + 5f + g + 3h + 2i + 6j + 4k + 5l + ... (I displayed two cycles), where a is the units, b the tens, etc.

example :
6594 6*6 + 2*5 + 3*9 + 4 = 36 + 10 + 27 + 6 = 77
77 is further dissolved into 3*7 + 7 = 28.
28 is 3*2 + 8 = 14
and finally 3*1 + 4 = 7.

This would be the 1-3-2-6-4-5 cycle.

Lovely work, Facial!

Here's my own algorithm... I think it's less beautiful, but easier to apply mentally. The idea is to quickly reduce some number by a factor of ten to another number which will be divisible by seven iff the first number is divisible by seven. This can be applied recursively.

Each recursion is simple enough. Just add or subtract a multiple of seven to reach a multiple of ten:
If the last digit is 1, subtract 21 and divide by 10.
If the last digit is 2, add 28 and divide by 10.
If the last digit is 3, add 7 and divide by 10.
If the last digit is 4, subtract 14 or add 56 and divide by 10.
If the last digit is 5, add or subtract 35 and divide by 10.
If the last digit is 6, add 14 or subtract 56 and divide by 10.
If the last digit is 7, subtract 7 and divide by 10.
If the last digit is 8, subtract 28 and divide by 10.
If the last digit is 9, subtract 21 and divide by 10.
If the last digit is 0, divide by 10.

eg: 6594
6594-14 = 6580
658-28 = 63
7|63, therefore 7|6594.

In principle, the same algorithm can be used to test divisibililty by any number. In practice I find I can do it for all 2 digit primes... but not necessarily reliably :).

I like the 11 multiplication trick.
Split and add.
Split the numbers, and put their sum in the middle...
11 * 43 = 473
11 8 32 = 352

I especially like it because no one taught it to me - I figured it out on my own when I was a kid.

Conversely, you can check for divisibility by eleven through the difference of the sums of the even and odd digits.
If the difference is divisible by 11 (usually it will be zero or 11), then so is the number:

eg 17498745
1 + 4 + 8 + 4 = 17
7 + 9 + 7 + 5 = 28

28 - 17 = 11

So 11 divides 17498745

Conversely, you can check for divisibility by eleven through the difference of the sums of the even and odd digits.
If the difference is divisible by 11 (usually it will be zero or 11), then so is the number:

eg 17498745
1 + 4 + 8 + 4 = 17
7 + 9 + 7 + 5 = 28

28 - 17 = 11

So 11 divides 17498745
If it's divisable by 11, or if it's zero.

Cool.

If the last digit is 1, subtract 21 and divide by 10.
If the last digit is 2, add 28 and divide by 10.
If the last digit is 3, add 7 and divide by 10.
If the last digit is 4, subtract 14 or add 56 and divide by 10.
If the last digit is 5, add or subtract 35 and divide by 10.
If the last digit is 6, add 14 or subtract 56 and divide by 10.
If the last digit is 7, subtract 7 and divide by 10.
If the last digit is 8, subtract 28 and divide by 10.
If the last digit is 9, subtract 21 and divide by 10.
If the last digit is 0, divide by 10.

eg: 6594
6594-14 = 6580
658-28 = 63
7|63, therefore 7|6594.

In principle, the same algorithm can be used to test divisibililty by any number. In practice I find I can do it for all 2 digit primes... but not necessarily reliably :).

Excellent - I believe this is even faster.

The problem with the 132645 cycle I derived is that it isn't necessarily faster than by plain brute force dividing.

Anyone know the division by zero rule? ;)

nevermind

Wow, what an old thread, but quite an eternally interesting topic nonetheless.

Now the question is why there is no efficient algorithms for determining divisibility by higher and higher prime numbers... it could be obvious, but something is telling me that it's not so.

Well there probably ARE algorithms, but they probably become much too complicated to do in your head.

How about the "missing one" trick?
Where, if you add an extra one to certain sequences, and take it out, or subtract it later, it still creates something in the sequence; like a sort of "convergence factor".
It don't work 'less you add the magic '1'.
A name for this algorithm is "Egyptian fraction(s)". A three-term eqn. looks like: 1/a\; +\; 1/b\; +\; 1/c\; =\; \frac {(d-1)} d
There are exactly 14 solutions, given a, b, c and d are all positive integers. It lets you determine a sequence of prime fractions, say, with a non-prime fractional remainder.

there is 3 small 'o's in the middle of the 3...acknowledgement of a higher order
1=i
2=us
3= god or higher order

Have you noticed how nature adheres to Fibonacci?

Yes, I spend many happy hours examining sunflowers.