Search found 64 matches
- Wed Mar 17, 2021 10:14 am
- Forum: Number Theory
- Topic: Calculating modular inverses of p mod $2^p$
- Replies: 2
- Views: 663
Re: Calculating modular inverses of p mod $2^p$
After some experimentation it turns out that if $p=2k+1$ then the inverse of $p$ mod $2^p$ is $\frac{k\cdot2^p + 1}{p}$. Which is $2^{p-1} - \frac{2^{p-1} - 1}{p}$, explaining the observation that it's slightly smaller than $2^{p-1}$. A variant approach is to use the form of Fermat's little theorem...
- Wed Feb 17, 2021 11:33 pm
- Forum: News, Suggestions, and FAQ
- Topic: Number of solvers for the latest 160 problems
- Replies: 16
- Views: 1202
- Thu Jan 28, 2021 3:33 pm
- Forum: News, Suggestions, and FAQ
- Topic: Can Project Euler require users to not post their solutions online?
- Replies: 8
- Views: 1040
Re: Can Project Euler require users to not post their solutions online?
Are you sure that this is the case? Here is an example from personal experience, back when I was solving problems as 'vamsikal3', I was 100% a member of the Project Euler community based on hk's interpretation. Then, I ran into PE 152. Based on my mathematical background at that time, I ran into a ...
- Thu Jan 21, 2021 12:40 pm
- Forum: Discrete Mathematics
- Topic: Counting constrained squarefree numbers
- Replies: 4
- Views: 1257
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: 1257
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: 6909
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: 358
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: 417
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: 1224
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: 1189
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: 1754
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: 23137
- Tue Oct 20, 2020 8:50 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 371
- Replies: 42
- Views: 23137
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: 1189
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: 1281
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: 4370
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: 1459
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: 1459
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: 15
- Views: 4642
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: 3082
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.