Search found 61 matches
- Thu Jan 21, 2021 12:40 pm
- Forum: Discrete Mathematics
- Topic: Counting constrained squarefree numbers
- Replies: 4
- Views: 47
Re: Counting constrained squarefree numbers
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 ...
- Thu Jan 21, 2021 8:26 am
- Forum: Discrete Mathematics
- Topic: Counting constrained squarefree numbers
- Replies: 4
- Views: 47
Re: Counting constrained squarefree numbers
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 ...
- Sat Jan 02, 2021 10:46 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 684
- Replies: 16
- Views: 5958
Re: Problem 684
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 ...
- Fri Jan 01, 2021 8:53 am
- Forum: Discrete Mathematics
- Topic: How to list all powerful numbers below N in $O(\sqrt{N})$time?
- Replies: 1
- Views: 111
Re: How to list all powerful numbers below N in $O(\sqrt{N})$time?
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...
- Tue Dec 29, 2020 9:34 am
- Forum: Discrete Mathematics
- Topic: How to compute a two-variable recurrence function C(n,n) in O(n) time?
- Replies: 2
- Views: 141
Re: How to compute a two-variable recurrence function C(n,n) in O(n) time?
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...
- Tue Dec 15, 2020 7:02 pm
- Forum: Number Theory
- Topic: Books in Number Theory
- Replies: 1
- Views: 528
Re: Books in Number Theory
This has been asked before, and it's not a question where the answers change very fast so: viewtopic.php?f=2&t=2931
- Thu Dec 10, 2020 8:07 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 737
- Replies: 2
- Views: 864
Re: Problem 737
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 ...
- Fri Nov 13, 2020 8:41 am
- Forum: News, Suggestions, and FAQ
- Topic: Website Update (12 Nov 20)
- Replies: 8
- Views: 1163
Re: Website Update (12 Nov 20)
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 $$.
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 $$.
- Wed Oct 21, 2020 1:01 pm
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 371
- Replies: 42
- Views: 21474
- Tue Oct 20, 2020 8:50 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 371
- Replies: 42
- Views: 21474
Re: Problem 371
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...
- Tue Oct 13, 2020 11:57 am
- Forum: News, Suggestions, and FAQ
- Topic: Suggestion for new awards
- Replies: 3
- Views: 737
Re: Suggestion for new awards
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" ...
- Thu Oct 08, 2020 7:29 am
- Forum: Clarifications on Project Euler Problems
- Topic: What kinda math should i know?
- Replies: 2
- Views: 1048
Re: What kinda math should i know?
"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...
- Mon Oct 05, 2020 7:45 pm
- Forum: News, Suggestions, and FAQ
- Topic: "You are the nth person to solve this problem"
- Replies: 5
- Views: 4066
Re: "You are the nth person to solve this problem"
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...
- Tue Sep 29, 2020 8:30 am
- Forum: Recreational
- Topic: big O notation of PE problems
- Replies: 3
- Views: 1135
Re: big O notation of PE problems
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 ...
- Tue Sep 22, 2020 8:27 am
- Forum: Recreational
- Topic: big O notation of PE problems
- Replies: 3
- Views: 1135
Re: big O notation of PE problems
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...
- Sat Sep 19, 2020 11:55 pm
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 710
- Replies: 14
- Views: 3629
Re: Problem 710
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...
- Mon Sep 14, 2020 8:21 am
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies: 10
- Views: 2578
Re: How to enumerate/count the numbers of a particular form below N in an efficient way?
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.
- Thu Sep 10, 2020 2:56 pm
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 004
- Replies: 85
- Views: 26325
Re: Problem 004
@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...
- Wed Sep 09, 2020 8:51 am
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies: 10
- Views: 2578
Re: How to enumerate/count the numbers of a particular form below N in an efficient way?
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...
- Mon Sep 07, 2020 5:44 pm
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies: 10
- Views: 2578
Re: How to enumerate/count the numbers of a particular form below N in an efficient way?
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...