Aeternus

You might want to look into Stirling's approximation and the bounds on the error there (the error is guaranteed to be within a certain bound dependent on n). Using some log rules, and choosing a decent enough constant for the [math]\Omega[/math] condition should make it all work out nicely.

For [math]\log(n!) = O(n \log n)[/math] consider that, [math] \log(n!) = \log(\prod_{i=1}^{n}{i}) [/math] which given [math]\log(a*b) = \log(a) + \log(b)[/math] is [math] \log(n!) = \sum_{i=1}^{n}{\log(i)} [/math] Now remember that, log is monotonic, it preserves order, ie we have [math] \forall\,x,y \in \mathbb{R} : x > y \Rightarrow \log(x) > \log(y) [/math], meaning we know [math]\log(n) > \log(n-1)[/math] so we have [math] \sum_{i=1}^{n}{\log(n)} \ge \sum_{i=1}^{n}{\log(i)} [/math] So [math] n\log(n) \ge log(n!) \,\forall \, n \ge 0 [/math]

Depends on what you are expecting from CS and where you are doing it. Perhaps you can elaborate a bit?

Yes, so given this http://en.wikipedia.org/wiki/Bertrand%27s_postulate , it seems what I suggested is always the case, and therefore it also seems that there is no solution to y^2=x! for some integers y and x. Given the argument I presented above it seems that this applies to y^n=x! as well (since if you always end up with that odd prime, you can never have 3 of them or 4 of them etc before getting a new odd prime). I imagine this is probably fairly well known and considered quite trivial (either that or I've gotten something wrong but it seems fairly straight forward).

I'm pretty sure this is not the case here in the UK. I wouldn't suggest that the title of professor is quite as restricted as in Germany but certainly there are a very limited number of professors compared to lecturers from what I have seen and it is definitely higher up in the academic food chain. http://en.wikipedia.org/wiki/Professor#Most_other_English-speaking_countries

Given for [math]y^2 = x![/math] to hold, the prime factors of all the numbers in the factorial sequence need to even out and until very large numbers (or possibly forever? would have to check), you will always get a new prime [math]q[/math] (an actual prime, not one of the factors of a composite number) after having just got a prime [math]p[/math] before you get [math]p[/math] again as a factor of another number in the factorial sequence. I.E you always (at least until large numbers?) have something of the form - [math] p ... q ... 2p [/math] where p and q are primes and therefore won't be able to find such a number where every prime in the sequence of prime factors of the factorial has a twin until this property no longer holds. Perhaps by looking at the formula/approximation for density of primes (perhaps taking some lower bound), one could either show that this always occurs or at least some similar property/extension prevents it, or at least offer a lower bound on the factorial for which it occurs?

*sigh* Hollywood really need to leave books alone

http://gmplib.org/ or take a look at some of the stuff here - http://www.google.co.uk/search?q=C+precision+number+library&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a

I love Firefox and all but could you back up that statistic? (It'd be nice to use as evidence in future)

You suggested that you are testing every pixel to try and find a solution. This is not what is being suggested. If you look at the wikipedia article, the iterative solution involves choosing a guess and then iteratively improving this guess by use of an equation that converges to a solution. I assume you would most likely stop when two answers remain in a single square pixel (ie sufficient accuracy for you). This is clearly not the same as testing every pixel. Using such a system you wouldn't have to have a list of all the possible pixels and their distances. Even with your current method, you only really need to keep track of the current smallest distance (ie, why keep track of all of them in a large array when only storing the current minimum and comparing as you go would work just as well (well better as the space complexity will be better)). Sorry if I have misunderstood what you are doing.

If you want to find the smallest number in a list, it's quicker to just keep a record of the current smallest number and go through the list comparing and replacing that current number with a new one if it's smaller rather than sorting and then just taking the first. The fastest sorting algorithm will likely be O(nlogn) whereas the simple linear search is O(n). Considering your overall method of calculation, I'm pretty sure there are iterative solutions to this problems that work on the points themselves to converge to a solution rather than trying all possible solutions, which would probably be quicker (See http://en.wikipedia.org/wiki/Geometric_median#Computation ).

Perhaps you are misunderstanding what infinity means in this case, it doesn't mean that there is some value infinity at which we can take an element and then that element has infinitely many digits. Infinity in this case simply expresses the concept that there is no maximum natural number, here you have to understand, that does not mean that there is/are a/some natural number(s) that is/are infinity (which is what such natural numbers you describe with infinite decimal expansions seem to amount to), but simply that there is no largest natural number (ie [math]\infty [/math] is the Supremum of [math]\mathbb{N}[/math]). You seem to assume that because there is no largest natural number, that there must be some element infinity, but this isn't the case, if you consider the generation of the natural numbers by starting at 0, and then simply taking the successor (+1, s(?) etc) and you continue to do this as much as you like, you will never reach some number with an infinite decimal expansion (ie infinity), adding one to any finite number will still produce a finite number.

Oops Don't know why I did that :\

I'm pretty sure [math] \forall x \in \mathbb{N} : \textrm{x has a finite decimal expansion} [/math]. In your example here with a number with infinitely many 3 digits, just because there are numbers with increasing numbers of three digits, and there are infinitely many of these, does not imply that there are numbers of infinite size/length. You might say that as you enumerate the numbers the number of digits tends to infinity but that is not the same as saying there is an element in the natural numbers with an infinite decimal expansion. I'm pretty sure if such number were to exist in [math]\mathbb{N}[/math], various things such as the Peano axioms wouldn't hold. Secondly, Cantors diagonalisation argument is very general, it doesn't require a certain method of enumeration, it only posits that one exists and goes on to show that given any enumeration an element can be produced that is in the reals (although the argument is easily generalised to lots of different uncountable sets) but will not be produced by the enumeration. I could be wrong, so someone please correct me if so. [edit] If you are suggesting that you can take infinitely many natural numbers together somehow, then I think you are misunderstanding what it means for a set to be countable ( http://en.wikipedia.org/wiki/Countable ). I have noticed you have a little "proof" that there must exist numbers in the natural numbers with infinite decimal expansions. You seem to suggest that because there are infinitely many natural numbers with increasing finite decimal expansions that there must exist a natural number with an infinite decimal expansion. As I said above, just because something "tends" to something, doesn't mean that something exists. I'm sure someone else can explain this better than me. Your example simply proves that for a given n digits, a number with n+1 digits must exist, this shows that there is no maximum n number of digits (ie the number of digits TENDS to infinity) but does not show that there is a number in the set with infinitely many digits. Note that you have assumed a number with n digits, which has a finite number of digits, adding 1 digit to it will never make it infinite.

Sounds like the beginning of Hitchhikers Guide to the Galaxy (where a woman finally realises the answer to the ultimate question and the planet is destroyed to make way for a space highway ) but given that you seem to be suggesting it spans an entire book and is explored a bit deeply not in a humourous way, I assume that isn't it

As I understand it, home students pay only a portion of the full fee and the rest is subsidised by the government, which I assume gets the money from the tax paid by the home students and their families and other tax payers in the UK who in general will benefit from the home student gaining an education. International students are made to pay the full fee, as in general if they are not paying said tax, then why should their fees be subsidised by the British government? There is also the second point, that even if they do somehow pay tax, a large portion of international students won't necessarily stay in the country upon graduation which means that the people who are paying tax towards said subsidies, but who are not going to University themselves are cheated, because their tax money would be going towards something which would not benefit them. I'm not necessarily agreeing or disagreeing with this mentality but I certainly wouldn't argue it's unfair within the current political system (both in Britain and worldwide). Perhaps there is some way you can get the Pakistani government to help subsidise some of the fee?

I haven't seen anything happening that forces a need for this sort of thing... While certainly scientists should consider the ethical implications of their work, I think some set of rules apparently made to make the general public happy is destined for disaster.

This will teach the little *beep*s ?

Oops, sorry. It completely slipped my mind, it was about 12:30am at the time.

[hide]Keith is 30 and Joseph is 18. Working Backwards to get equations - "Their combined ages make forty eight." K + J = 48 "when Keith was three times as old as Joseph" (K - y) = 3(J - y) for some given y years ago. "Joseph is three times as old as Keith was when Keith" - Hence 3 x Keiths age in the above equation 3(K-y) "Keith was half as old as Joseph will be when Joseph is" - So half the above age 3(K-y)/2 "Keith is twice as old as Joseph was when Keith" - So Twice Josephs age from the above equation for Keiths age, so Keiths age minus the difference between them - K = 2(3(K-y)/2 - (K-J)) Now reduce the equation a little K = 3(K-y) - 2(K-J) K = 3K - 2K -3y -2J 3y = 2J y = 2J/3 So we now have 3 equations in K,J, and y - K + J = 48 (K-y) = 3(J-y) y = 2J/3 So substitute to solve - (K - 2J/3) = 3(J - 2J/3) K - 2J/3 = 3(J/3) K - 2J/3 = J K = 5J/3 K + J =48 5J/3 + J = 48 8J/3 = 48 J = 18 K = 48 - 18 = 30[/hide] Hopefully that's right

The problem you have here is that either you have a finite limit on the n that can be calculated, or if you don't, space isn't O(1) since precision number systems will invariably use more space for large numbers which will mean the space required will increase as n increases (as the result will be a much much larger number which will need more space to store precisely). The same issue occurs with the time complexity, O(n) only holds when you have finite integer types which have constant time operations. When you begin to deal with large values of n and need some form of precision number system, you encounter the problem that larger numbers are harder to calculate with meaning the operations on such numbers aren't O(1) which means the factorial calculation is no longer O(n). Lisp is great though

Assuming they are lists, the easiest way would be just to use python lists sort() method (which I think uses a variation on quicksort called samplesort (ref)) and then go through linearly to find the duplicates. You will still get O(nlogn) performance although the constant involved will be slightly bigger due to that additional linear search. You'll still get much better performance than you are getting with fairly minimal effort.

Well it was a fun challenge I will almost certainly come back to the stuff I have at some point to make improvements, I just need to do more reading up on certain areas to approach some of the more elaborate algorithms I want to use. I recently got my project/dissertation topic sorted so I will probably be more interested/busy with that in the near future It'd certainly be nice to have this sort of challenge again Perhaps next time there could be several components to the challenge with varying degrees of complexity or varying subject areas? I imagine there are many things where you could have a basic fundamental maths component first, then perhaps a programming exercise and then perhaps some kind of analysis exercise or something, I don't know, I haven't really thought it out fully but I'm just chucking the idea out as it might get more people involved.

Do you genuinely find washing windows all day interesting? I certainly wouldn't... That's not to say some people don't. I used to work part time in a Petrol station for a few years, the people were nice enough and the hours suited me but from my perspective the job was so mind numbingly boring that if I were to do it full time I imagine I would kill myself. My mother on the other hand, worked there for years before that (she is recovering from operations on her leg currently) and loved it as she could talk to the customers and enjoyed the atmosphere. I am not suggesting that people aren't inherently selfish animals, just that personal gain can be as simple as job/life satisfaction, there is a thrill for some people in a job well done or in doing something you feel is useful for society. Why do academics work at universities for less than they could earn in industry (excluding more extreme cases)?