[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 36 KB, 500x441, 1303426553380.jpg [View same] [iqdb] [saucenao] [google]
5290345 No.5290345 [Reply] [Original]

/sci/ I am plagued with curiosity.

Every divisibility test there is requires some form of recursion, however simple. For example, to see if a number is divisible by 2, just see if its 10^0 (ones) digit is divisible by 2. For 3, add up the individual digits and see if they are divisible by 3.

What I want to know is this: can there be a test which does not use recursion?

I think not because numbers are more "fundamental" than the number systems that we use to express said numbers. We mostly use base 10, so we need to work around numbers with powers of 10.

Please help for the love of all that is useless.

Pic entirely unrelated.

>> No.5290359

>>5290345
That first example is not really recursion, as you are not repeating anything - only dividing by 2 once. I don't think that's your question, could you clarify?

>> No.5290370

Well what I am saying is that to find if a number is divisible by two (or any number for that matter) we normally use some 'part' or aspect of that number and see if that is divisible. That is recursive because you are essentially testing divisibility for the same thing twice ( or more).

Sorry for the confusion. Also, I don't really get too much of this as well as I suddenly started thinking about this and I am pretty stupid.

>> No.5290381

>>5290370
I see your point. I'm not sure if anything like that exists, but I'm bumping for you in case someone does.

But hey, you could always use long division and make sure there is no remainder.

>> No.5290385

>>5290370
This only makes sense if we are given the number in its base representation, ie, in base 10, as you have assumed. It would be different in base 2, different in base 3, etc; and it would be much different if we were simply given a number, without information about the value in its places in a certain number system.

>> No.5290396

>>5290385
Yeah. So I guess what I'm saying is there something fundamental about any multiple of 'k' that we could see without using recursive methods which would obviously be specific to the number system.

Scary shit man.

>> No.5290405

shameless bump!

>> No.5290429

>>5290345 Every divisibility test there is requires some form of recursion

The fuck are you talking about?
if(X%3 == 0) X is divisible by 3
if(X%117==0) X is divisible by 117
if(X%19==0) X is divisible by 19.

This test is accomplished with a single AND operation in the processor. There is no recursion.

>> No.5290428

>>5290396
We can even specify numbers without a number system, and ask whether they are divisible by a certain other number. For example:

Let <span class="math">n[/spoiler] be the smallest positive integer such that any two-coloring of the complete graph on <span class="math">n[/spoiler] vertices must necessarily contain, as a subgraph, a monochromatic complete graph on 5 vertices.

Is <span class="math">n[/spoiler] even?

This, btw, is actually a really important and well-known problem in professional mathematics.

>> No.5290438

>>5290428

Notice how <span class="math">n[/spoiler] is not given in any number system, so we can't take advantage of that. In fact, <span class="math">n[/spoiler] is not really given at all, in the normal sense.

>> No.5290442

>>5290428
>well-known problem in professional mathematics

Fuck me. There goes my chance for getting it!

lol

>> No.5290465

>>5290429

OP here

I realized that the common divisibility tests are merely used for human convenience. Non-savants can't do 345546342 / 3 in their head quickly to see if it comes out to an integer.

This question actually arises from a bigger question; how can a computer tell if a number is prime?

I had a ridiculous train of thought that is hard to piece together into coherent sentences on the internet. And it's all probably bull too.

So close!

>> No.5290474

>>5290465
>how can a computer tell if a number is prime?
if the remainder is not zero when you divide the number by the numbers from 2 to the number-1, then the number is effectively prime.

>> No.5290499

>>5290474
What does "effectively prime" mean?

>> No.5290517

>>5290499
It means that it doesn't take into account negative numbers, which are all composite numbers, or numbers between 0 and 1.

>> No.5290534

>>5290474
Also, can you explain that? I don't know what you're talking about when you say it divides from 2 to -1.

>> No.5290546

>>5290534
Sorry for the lack of clarity, here is a c++ function which shows what I mean:

bool IsPrime(int number)
{
for(int x = 2; x < number; x++)
{
if(number % x == 0)
{
return false;
}
}
return true;
}

>> No.5290566

>>5290534
say you want to know if a number, call it n, is prime, when he (>>5290474) says "numbers from 2 to the number-1" he means "numbers from 2 to n-1"

>> No.5290572

>>5290345
>What I want to know is this: can there be a test which does not use recursion?
By the Church Turing Thesis, no not really.

>> No.5290604
File: 154 KB, 445x369, Sieve_of_Eratosthenes_animation[1].gif [View same] [iqdb] [saucenao] [google]
5290604

>> No.5290619

You are on to something. Note that 1, 2, 5 and 10 are the only numbers that have non recursive tests ("is the last digit divisible by 2?"). This is because we use base 10 and 10 is divisible by 1, 2, 5, and 10. Different bases have different division rules. Base 7 has a nifty divisibility rule for 7 ("Is the last digit 0?) and base 9 has a nice divisibility rule for 3.

This is why people have argued that we should use base 12. 12 is divisible by 1, 2, 3, 4, 6, and 12. We could have nice divisibility rules for all of those numbers. Not so with base 10.

>> No.5290627

>>5290474
>dividing all the way up to n-1
>not stopping at the square root of n
>using a non-polynomial time algorithm


Pleb.

>> No.5290684

>>5290627
>>not stopping at the square root of n
Holy fuck, that's genius. I didn't even consider that.

>> No.5290687

>>5290684
is this your first year in comp sci?

>> No.5290694

>>5290619
wouldn't that same argument for base 12 be used for base 6

>> No.5290700

>>5290694
Well, it wouldn't be divisible by 4 or 12

>> No.5290727

OP here, I just wanted to thank you guys for the responses. I also want to know, is there a good way this can be applied to finding prime factorization of numbers in computation, that isn't just testing out all the prime numbers up until a given value?

captcha: 473-1658 romcali

>> No.5290730

>>5290727
Not really, no. For specialized applications, there might be slightly better algorithms. If the domain is small enough and you have enough memory / disk to throw at the problem, you can precompute the answers.

>> No.5290743

>>5290730
Why is that, if I may ask?

>> No.5290756

>>5290727
There are plenty of different ways that are faster than that.

http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests

>> No.5290759

largest prime number currently known is
4737(2^985810) + 1

>> No.5290764

>>5290759
my bad that's the 10th
https://en.wikipedia.org/wiki/Largest_known_prime_number

>> No.5290766

>>5290759
>>5290764
>10th
fuck, nevermind

>> No.5290779

>>5290627
Can you explain? I'm interested yet young and ignorant.

>> No.5290828

>>5290779
>polynomial time
http://en.wikipedia.org/wiki/Time_complexity#Polynomial_time

>> No.5290839

>>5290779
I'm not the one whose post you're replying to, but:
Each divisor (q) of a number (n) must have some other divisor (r) which, when multiplied by q, yields n. Example: divisors of 12 are {1, 2, 3, 4, 6, 12}. The pairs are {{1, 12}, {2, 6}, {3, 4}}. The square root of 12 is about 3.464. Notice how in each pair of divisors, one of the numbers is less than the square root, and the other is greater than the square root. Worst case scenario for any number, both numbers in one of the pairs happen to be the same number (e.g. 16 has the divisor pair {4, 4}). Since we only need to find one number (besides 1 and itself) that evenly divides a number n for n to be nonprime (composite), we really only need to check up to the square root of n.

As for the polynomial time, that refers to how many operations you need to perform (arithmetic, etc) in the worst-case scenario for the algorithm. If the time is polynomial, then as the input increases, the number of operations performed in the worst-case scenario increases as a function of some polynomial rather than less pleasant things like exponentially or (God forbid) factorially.