/sqt/ - Stupid Question Thread: Sponsored by Crispr™ Edition

Suppose that [math] k [/math] is a positive integer. Now suppose that for all positive integers [math] n [/math], the number [math] n^2 + n + 1 [/math] has at most k distinct prime divisors.

Does a contradiction arise from this or does such a k exist?

why do you think such a k exists?

No, I doubt such a k exist. In fact, I want to prove that such a k doesn't exist.

But I can't seem to find a contradiction if I assume this k exists.

Steps are unphysical as you'll need delta function forces.

k is at least 4

k shouldn't exist and that is what I am ultimately trying to prove.

I am trying to find what contradiction arises from assuming k exists.

This is equivalent to asking how many prime factors [math]n-\zeta[/math] can have, where [math]\zeta[/math] is a primitive cube root of unity. It should be easy to check this is arbitrarily high.

Could you explain the connection further?

Sure. You can factor n^2+n+1 as [math](n-\zeta)(n-\zeta^2)[/math] in the ring [math]\mathbb Z[\zeta] [/math] (ignore the last bit if it means nothing to you). If you happen to know, this ring is what's called a unique factorization domain, do we can factor elements uniquely into primes just like with the integers, although primes in this ring might look slightly different. Basically, the primes in this factorization will combine together in pairs to give the integral primes you're looking for.

It's the first time I've heard most of those terms. Could the argument you are making be re-phrased in more elementary terms? As in, only involving elementary number theory?

Yeah, ignore the fancy terms of you don't know them. The heart of the argument is elementary: you have a polynomial over the integers. I want to factor it so that I can more easily look for lots of prime factors. The only problem is that this polynomial doesn't factor over the reals. This isn't a big deal though -- I'll just factor it over the complex numbers. So this amounts to taking your integer n^2+n+1 and rewriting it as the product of two complex numbers that are almost like integers and then trying to factor those further. From here, just find a way to make arbitrarily large products that come out to n-\zeta

A farmer wants to build a fence along a river. He has 500 feet of fencing and wants to enclose a rectangular pen on three sides (with the river providing the fourth side). If xx is the length of the side perpendicular to the river, determine the area of the pen as a function of xx.

can someone please explain why the equation is 2x(250-x) or x(500-2x)?

Why is the empty set empty if it contains itself? If containing itself doesn't matter because it's empty, then why is its power set not empty?

>Why is the empty set empty if it contains itself?
because it contains no elements

> If containing itself doesn't matter because it's empty, then why is its power set not empty?
because P({})={ {} }

So, I'm trying to complete a challenge on Rosalind where I write a function that simulates the fibonacci sequence but with the modification that the rabbits die after m turns (i.e. a generalization of the Padovan sequence). I have a code that works but the problem is that it's too slow.

I'm a total noob when it comes to programming. I simplified the code to the best of my abilities, but it still takes several minutes to simulate more than 50 turns and lifespans higher than 12, and the challenges are timed.

Can I solve this by using a better computer, or is it strictly a code issue? The computer (our lab computer) has 4GB of RAM and an Intel 3.17 GHz processor.

The code is:

def fib(n):
if n == 1:
return 1
elif n == 2:
return 1
else:
return fib(n-1) + fib(n-2)

def fibd(n, m):
if n < (m+2) and m > 3:
return fib(n)
elif n < (m+1) and m == 3:
return fib(n)
elif n >= (m+1) and m==3:
return fibd(n-2, m) + fibd(n-3, m)
elif n >= (m+2) and m > 3:
return sum(map(fibd, [n-(m+x) for x in (range(-(m-2), 2))], [m]*m))

This is Python, in case that wasn't obvious.

It is strictly a code issue, and a fairly famous one.

Imagine you are computing fib(50). Then it computes fib(49) + fib(48). Which gets computed as (fib(48) + fib(47)) + fib(48).

Which means that in computing fib(50), you are computing fib(48) twice.

Each of those fib(48) computations also computes fib(46) twice. So that's four computations of fib(46). (More, in fact. But this is bad enough already.) Eight computations of fib(44). I'm sure you can see where this is going. To see this in action, try adding a print statement to the start of the fib() function, that prints n.

The right solution is to compute fib() iteratively. This takes the form of a nonrecursive function, structured around a loop that computes fib(n) for increasing values of n. This results in an algorithm that is exponentially faster.

The same consideration above applies to fibd() as well, in a modified form. I suggest you try to fix fib() in this way first -- fib(50) should be computed instantly -- and then apply the same techniques to fibd().

(Also, please never paste code directly into Veeky Forums again. This is particularly bad with python, because Veeky Forums eats your indentation, which python needs.)

Thanks, is there a resource for dumb people that gives examples of transforming recursive functions to iterative functions like you said? I will Google/stackexchange this but am basically totally new to coding. I only started two weeks ago.

The distribution of factual knowledge is fundamental to the advancement of society. You help humanity by smugly scoffing at those who know a little less than you do about the principles of nuclear fusion

is that calc I? lul

can anyone help me with this? why is it happening?

I'm not smug about it

Can i self-study group theory with having only done up to calculus? (I don't know very much linear algebra, only basics of matrices)

yes, try pic related