Determination of a factor in base 2 (human only)

Community Forums/General Help/Determination of a factor in base 2 (human only)

Shortwind(Posted 2010) [#1]
Everyone should know that it is simple to know if 2 (even) is a factor of any base 2 number by looking at the last digit. If it's 0 (zero) it is even (divisible by 2).

Now (for example) in base 10, you can tell if a number is divisible by 5 just by looking at the last digit. If it is 0 (zero) or 5 then 5 is a factor.

Going back to base 2 (or other bases), are there any other number curiosities? In other words, is there a way to just look at a base 2 number and know without doing any calculation that 3 is a factor?

:::Off topic:::
For another example, if you add up (in base 2) all the pairs of bits, and the answer is divisible by 3, then the whole number is divisible by 3.) (Works in base 10 as well, as you probably know.)
:::On topic:::

Is there any other quick secrets for other prime numbers in base 2 or base 10? What about 5 in base 2? (Without actually dividing (mod) the number?)

Just interested to see if anyone knows any other curiosities. (7, 11)

thanks,
:D

P.S. No this is not some form of trying to figure out how to make a computer factor faster. This is just a curiosity of mine to determine if anyone knows any other humanly fast methods for determining the factor of a given number.


xlsior(Posted 2010) [#2]
You can do binary math:
if the last number is 0, it's divisible by 2 (and therefor an even number)
if the last two numbers are 00, it's divisible by 4.
If the last three numbers are 000, it's divisible by 8
If the last four numbers are 0000, it's divisible by 16
if the last five numbers are 00000, it's divisible by 32
etc.

Other than that, I think you''ll have to do actual math.


Matty(Posted 2010) [#3]
eDIT - removed.

Last edited 2010


Floyd(Posted 2010) [#4]
Warning: I started to type a brief comment and it just kept growing. Still, it's fairly interesting to a math geek.

I never thought about looking directly at a binary number for factors. But I can see some possibilities.

In base ten the easy rules are derived from two ideas. First, 10 = 2*5 means you check for divisibility by 2,5 just by looking at the last digit. Likewise you can check for divisibility by 4,25 using last two digits, by 8,125 with last three etc.

The second idea is for numbers which are +1 or -1 base ten. The fact that 10 is +1 mod 9 means that 10^2, 10^3 etc. are all 1 mod 9. As a result a number is congruent mod 9 to the sum of the digits. This process can be repeated. Example: for 32718 we add digits to get 21, then again to get 3. This means 32718 is congruent to 3 mod 9 and thus not divible by 9.

Likewise 11 - 1 = 10 gives a test for divisibility by 11. We note that 10 is -1 mod 11. From that we know 10^2 is (-1)^2, or 1. 10^3 is -1, 10^4 is +1 and so on. So a number can be reduced by the sum of digits method, but alternating + and -, starting with the rightmost digit.

Example: For 76208 we have 8 - 0 + 2 - 6 + 7 = 11 and then 1 - 1 = 0.
Thus 76208 is 0 mod 11 and is divisible by 11.

The same tricks will work in binary, although a maximum digit of 1 doesn't provide much leeway. But you can use pairs of bits and consider the number as base 4, or triples of bits for base 8 etc.

With pairs of bits, base 4, we then get rules for 3,5. Triples are base 8 so we can do 7,9. The practical limit for human readability is probably blocks of four, which is base 16 and we get rules for 15,17. These are all analogous to the 9,11 rules for base 10.

Example: n = 110101101. Let's group pairs of bits 1 10 10 11 01. These give base four digits of 1 2 2 3 1. To reduce mod 5, remembering that 5 is -1 mod 4, we calculate

1 - 3 + 2 - 2 + 1 = -1. So n is congruent to -1 mod 5 and not divible by 5.

As a reality check n = 110101101 is 429 in base 10. This is congruent to 9 mod 5, and 9 - 10 = -1 so n is also congruent to -1 mod 5.

Last edited 2010


Shortwind(Posted 2010) [#5]
Very interesting read Floyd, thanks.

To expand on what xlsior said:

Given any binary number with a string of zeros, after rotating out the zeros (dividing by 2) if the rest of the digits is a prime number your done.

Example:

110 = 3 * 2^1 = 6
1100 = 3 * 2^2 = 12
11000 = 3 * 2^3 = 24
110000 = 3 * 2^4 = 48

1010 = 5 * 2 = 10
10100 = 5 * 4 = 20
101000 = 5 * 8 = 40

1110 = 7 * 2 = 14
11100 = 7 * 4 = 28
111000 = 7 * 8 = 56

As you can see, it is clearly simplier to identify the factors of some types of numbers in base 2 than it is in base 10. (Unless you've got your times tables memorized very well.)

:D

Last edited 2010


jankupila(Posted 2010) [#6]
You can sum the numbers of an example number and if the result is divable with three, the example number is divable by three. If the sum is big or you can't tell if it is divable by three you can sum up them again.

and offtopic,

If you have continuous number for example 2,23232323232323232323... and you want to know which fraction it is, you tell it that way: you take the number what repeates and divide it by 9, 99 ,999 depending the size of continuous cycle. In our example the cycle is 23. You divide it by 99. The result of the 2,232323.. is 2+23/99.

Last edited 2010


marksibly(Posted 2010) [#7]
Hi,

> You can sum the numbers of an example number and if the result is divable with three, the example number is divable by three.

This one has always made me curious.

Is this a known mathematical 'truth', or does it just happen to be true for all the numbers I've tried it with?!?

I can grok the low bit being 0 meaning a number is even intuitively (ie: I can construct a proof in my imagination!), but the factor of 3 one is harder to get to grips with.

Which is probably why I suck at math - took me years to work out for myself where the 'borrow 1' comes from in subtraction!


jankupila(Posted 2010) [#8]
You can say that it is mathematical truth, I learned it in elementary school.


Warpy(Posted 2010) [#9]
I will prove it's true:
The remainder when you divide 10^n by 3 is always 1, for any positive whole number n. This is because 10^n is one more than 999...9 (the number whose digits are n nines).

Further, the remainder when you divide 2*10^n by 3 is 2, because 2*99...99 is 199...98, and 2*10^n is two more than that. The remainder on dividing 3*10^n by 3 is 0 because it's a multiple of 3, and dividing 4*10^n by 3 leaves remainder 1 again, and so it carries on.

For brevity, the remainder when you divide a by b is called 'a (modulo b)'.

b divides a only when a = 0 (modulo b), which is the same as saying there's no remainder when you divide a by b. (Fact 1)

So we've shown that for any whole number d, d*10^n == d (modulo 3). (Fact 2)

So let's say we've got a whole number i whose digits are (reading right to left) d0,d1,d2, ... ,dm.

Then,
i = d0 + d1*10 + d2*10^2 + d3*10^3 + ... + dm*10^m

but by Fact 2,
i = d0 + d1 + d2 + d3 + ... + dm (modulo 3).


Notice that the right hand side of that equation is the sum of the digits of i, which I'll call s.

So, by Fact 1: if s, the sum of the digits, is divisible by 3, then s=0 (mod 3). But i = s (mod 3), so i = 0 (mod 3). Which means that i is divisible by 3!