Algorithms

I want to see how many pointless, awesome algorithms can be amassed in this thread. Here are a couple simple ones oriented on saving time on simple arithimetic-

Any number can be divided by 9 if the sums of the digits add up to something divisible nine, e.g 513.

You can find the square root of an imperfect square that is a a perfect square with an additional zero with the following:

take 40- the first digit is 2, which IS a perfect square. The square root of 40 can then be found easily by multiplying 2 (root of 4) by the square root of ten; 3.16, which has been rounded down, obviously.

thus, the square root of 40 is 6.32.

The square of a two digit number ending in five can be attained by the multiplying the first digit by itself plus 1, and then simply multiplying the second digits.

75 x 75=

7x8=56

5x5=25

Therefore, it is 5625.

this next one will work with anything that has 0 in the middle for a place value, and also for 2 digit numbers that have the same first number as a place value.

403 x 407

Multiply the first two, add the third and multiply the sum by the first digit, and then multiply the third digits. Listing the products in that respective order will yield the answer. So, this problem would look like this-

164021. With 2 digits do the same thing, but add the products in this fashion;

16
 40
  21= 2021

anyway, start posting more so i can keep fapping to this

10 = 1 mod 3 =>
'abcd' = a*10^3 + b*10^2 + c*10^1 + d*10^0 = a*1^3 + b*1^2 + c*1^1 + d*1^0 = a + b + c + d mod 3

e.g. 34018734361 = 3+4+0+1+8+7+3+4+3+6+1 = 40 = 4 + 0 = 4 = 1 mod 3
=> 34018734361 is not divisible by 3

but 24018734361 is and 24018734361/3 = 8006244787

Let A be an integer in decimal expansion.  Let B be (the sum of the odd digits) - (the sum of the even digits).  A and B are congruent mod 11.

Euclid's algorithm
quicksort
mergesort
bubble sort
insertion sort
Dijkstra's algorithm
greedy algorithm

I seek a deterministic algorithm to solve the traveling salesman problem (NP complete) in polynomial time, but haven't accomplished that yet.  Can /sci/ help plox?

>>3
P≟NP
I think someone needs to work on this first, sir...
According to Wikipedia, which knows all, you can do it yourself in O(n!) time, but with dynamic programming, you can get it down to O((n^2)(2^n)).

>>3

I have a truly marvelous algorithm that solves TSP in polynomial time, but this textarea is too small to contain it.

>>5

Is it sad that I get the reference?

>>6
no, it's /sci/ afterall. It would be sad if you didn't get the reference.

a p-complete method for factoring primes

For any prime p...

whoops! forgot my hat

>>1

I never understood why digital sums (the sum of the digits that make up a number) have such weird properties. If someone would explain it to me I would greatly appreciate it. Also, I remember reading somewhere in the documentation for gnu's bignum library that the digital sum is used to find out if a number is a perfect square (It isn't exact, it just says if it's possible). Also, isn't the digital sum unique to the base the numbers are represented in (I'm sorry if I'm way off base here, I'm pretty drunk and having trouble thinking)?

http://en.wikipedia.org/wiki/Modular_arithmetic

Essentially, all numbers in decimal representation are
a + 10b + 100c + 1000d + ...
10^n is 1 mod 3, so using modular arithmetic, we see the digital sum result you want
10^n is also 1 mod 9, so the same applies to 9

It's not unique, but it does depend on the base the numbers are represented in.  The rule for 3 would work for base 4, 7, and any other number congruent to 1 mod 3.

Don't call me gay, but I need some mary jay!

Marijuana MUST be legalized.