Re:Any positive number can be written as a sum of three pali...
by shaded-enmity on Tuesday September 18, 2018 @12:45PM
(#18016835)
Yeah, for example to check if a number is divisible by 3, we can use the digit sum and check if the result is divisible by 3, e.g. 153=(1)+(5)+(3)=9.
This works in base-10, but we can generalize this by converting the dividend X into (3* X+1)-base then doing a digit sum.
Let's say we want to check whether 238 is divisible by 17, so our base is 3* 17+1=52, 238 in base-52 is (4)+(30)=34=2* 17.
If the convert-to-arbitrary-base operation was particularly cheap to compute, we could convert to base X+1 and check if the last number is 0 (same logic as: is_even = (i & 1) == 0) :)
[ Parent
| on HN ]
Re:Any positive number can be written as a sum of three pali...
by pishpash on Tuesday September 18, 2018 @01:55PM
(#18017574)
The convert to base X operation can't be cheaper than just dividing by X, can it?
Re:Any positive number can be written as a sum of three pali...
by industriousthou on Wednesday September 19, 2018 @01:14AM
(#18021841)
Is it unreasonable to think that some operations might be cheaper to compute by the converting the base and applying these types of tests?