Project Euler Forum

It seems that the formula above only holds when d is prime. Oops. You're quite correct. Where I said "which are not multiples of $d$" I should have said "which are coprime with $d$". Then an inclusion-exclusion follows as you indicate. The conclusion that this gives an approach ...

Let $d$ be a squarefree number, $S(n)$ count the squarefree numbers up to $n$, $S_d(n)$ count the squarefree numbers up to $n$ which are multiples of $d$. The numbers counted by $S_d$ are in bijection with the squarefree numbers up to $\lfloor \frac{n}{d} \rfloor$ which are not multiples of $d$, so ...

The brute force and medium algorithm both agree with S(20) = 1074 (the fast one only works on Fibonacci inputs). I think it's a legitimate hint to say that there's nothing special about Fibonacci inputs. My best guess is that the question asks for the particular Fibonacci-based sum that it does as ...

You don't want to do multiple sorts. What I would try is to use the characterisation that powerful numbers have a canonical representation $a^2 b^3$ where $b$ is squarefree. Calculate the squarefree numbers up to $\sqrt[3]{n}$ and then put these $b$s in a priority queue. For each $b$ the numbers gen...

Suppose we have a two-variable recurrence relation: $C(n,k)=C(n-1,k)+C(n,k-1)$ where boundary values such as $C(n,0)$ and $C(0,k)$ are given. For this specific example, first note that only addition is involved so the contributions of the $C(i,0)$ and $C(0,j)$ are independent. Then consider the pat...

This has been asked before, and it's not a question where the answers change very fast so: viewtopic.php?f=2&t=2931

My formulae seem a little bit off: the total angles for the numbers of coins given are about 3% off, but the error decreases for more coins. I don't think you should be concerned about that, as long as it's 3% over rather than 3% under. Bear in mind that those numbers given are for the first point ...

Possibly related to an earlier update, but I noticed it while reviewing my posts to see what threads I might want to watch:

Has something changed in the MathJax configuration? I'm sure my post https://projecteuler.net/thread=229;page=5#349423 used to have newlines from the \\ inside $$.

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" ...

"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...

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...