Project Euler Forum

hk wrote: ↑Tue Oct 20, 2020 9:26 am That post of mine is really a long, long time ago.

But the problem under discussion is still a problem, and the solution which I'm proposing is (AFAICT) new.

I fear that explaining in considerable more detail makes an otherwise nice problem almost unreadable. But the nonsense about numberplates has already made an otherwise nice problem almost unintelligible. It would be better to ditch that entirely and write a problem statement which only gives the ni...

They currently cover 1-200, 201-300, 1-400. The obvious continuation would be 401-600, 1-800. If there's a desire to add awards, Conquering Difficulties looks like another that could be extended. Possibilities include the obvious "Solve at least N problems at all of the difficulty levels" for higher...

"Elementary number theory" will help with an awful lot of them. "Enumerative combinatorics" is also a popular topic. It helps to be able to recognise a Markov process and know how to analyse it with linear algebra. There are plenty of probability questions, so you'll need to know what expectation is...

Adding extra data, like the position which it was solved to each member's profile, would not only add additional DB storage overhead, but it is not necessarily a fixed value and over time might begin to become inaccurate due to the reasons already mentioned. Yes, that would be a bad way of doing it...

edit: Do you know of any problems < 100 where the time complexity can be easily calculated? I know of some where it can be upper-bounded, but giving the bounds would be a partial spoiler for the solution. (In fact, once you've done a couple of hundred problems the size of the input often gives you ...

The subject of asymptotics confuses many people, and often needs careful statement to avoid confusing the rest. Big-O notation is a notation, that is to say, a representation. The representation is not the same as the thing it represents, which is the asymptotic behaviour of something. A statement t...

I am partially happy to report that my spreadsheet grew to 822 permutations, so now I am only missing two! Sorry, not so. E.g. compare columns RY and ACN, which by my reckoning are both (7, 2, 2, 2, 7). Also, the reason people aren't looking at your spreadsheet might be because it's a nuisance to t...

Maybe worth a quick note, then, that a basic sieve can enumerate all squarefree numbers, grouping them by number of prime factors, in $\tilde O(n)$ time.

@Ontogenes, you're looking for a number which has two properties: (1) it's a palindrome; (2) it's a product of two 3-digit numbers. There are three basic approaches: (A) generate all numbers and test both properties; (B) generate all numbers having the first property and test whether they have the s...

Actually, I'm now curious about: For trivial or specific cases, such as L={1,1,1,1} or L={2,1}, it is easy to come up with an efficient algorithm(I have a recursive algorithm for L={1,1,1,1}). My technique gives theoretical asymptotics of $O(N^{23/24})$ for $\{1,1,1,1\}$, which doesn't really seem p...

Got it, but can this implementation compute C(L,N) efficiently? For example, for the case C({5,5,3},$10^{18}$), we need an $O(N^{1/3})$ approach, and for the case C({7,7,5},$10^{30}$),we need an $O(N^{1/5})$ approach. I'm not quite sure why $O(\sqrt[\min(a_i)]{N})$ is the cutoff for "efficient". Lo...

No, they're indicator functions $I_L(n) = C(L, n) - C(L, n-1)$.

The sums involved are of the form $\sum_{k=1}^N f(k)\, g(\lfloor\tfrac{n}{k}\rfloor)$ where $f,g$ are indicator functions for $E(?,N)$.

I think you are already familiar with inclusion-exclusion, fast evaluation of the prime counting function, and sums of Dirichlet convolutions. Just put them together...

I think it's compatible with the aims and ethos of this site to say that it's easy to show that such an $F$ exists by strong induction: just take $\sigma(i\cdot j)=\sum_{x|i}\sum_{y|j}F(x,y)$ as defining $F(i, j)$. As to whether there's a more useful expression for it, one can use the inductive defi...

The problem statement says: We shall let the amount of space wasted in cubic metres be given by $V(x)$. If $x = 1.114785284$, which happens to have three squared decimal places, then the amount of space wasted, $V(1.114785284) \approx 36$. Given the range of possible solutions to this problem there ...

Solutions to $x^3 = 1$ are roots of $x^3 - 1$ which factors as $(x-1)(x^2+x+1)$. For $p \neq 2$ you can complete the square as over the reals, giving $x = 2^{-1}(-1 \pm \sqrt{-3})$. Square roots modulo a prime can be computed by the Tonelli-Shanks algorithm. Solutions modulo a prime power can be obt...

Just as an impression without actual timing data, the wait for the green tick seems higher than usual today. I don't know whether this is related to the maintenance, but I thought I'd mention it.

lucasart wrote: ↑Tue Aug 04, 2020 5:47 am PS: C and C++ are completely different ball games. They shouldn't be lumped together. It's obvious that this groupping was made by mathematicians, not programmers.

Bear in mind that the grouping was made two decades ago, when C++ had diverged much less from C than it has now.