News for hackers. Stuff that matters.
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) :)
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?
Re:Any positive number can be written as a sum of three pali... by pmiller2 on Wednesday September 19, 2018 @02:00AM (#18022055)
Referring specifically to divisibility tests, converting bases takes more work than just doing the division. What other operations were you thinking of?