Search found 65 matches

by pjt33
Tue May 04, 2021 7:53 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 756
Replies: 9
Views: 683

Re: 756

From what I understand E is like the expected value of Delta with n and m. But if delta is S - S*, where does the fraction answer of E(delta|k,100,50) = 2525/1326 come from? The fraction comes from expected . For any given tuple $(X_1, X_2, \ldots, X_m)$ the value of $S^*$ will be an integer, but y...
by pjt33
Wed Mar 17, 2021 10:14 am
Forum: Number Theory
Topic: Calculating modular inverses of p mod $2^p$
Replies: 2
Views: 1063

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...
by pjt33
Wed Feb 17, 2021 11:33 pm
Forum: News, Suggestions, and FAQ
Topic: Number of solvers for the latest 160 problems
Replies: 16
Views: 1950

Re: Number of solvers for the latest 160 problems

openBook wrote: Wed Feb 17, 2021 9:08 amI am interested in the number of unique solvers for problems in the range [600, 750].
Zero. The problem with fewest solvers is the most recent one, which currently has 61.
by pjt33
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: 1480

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 ...
by pjt33
Thu Jan 21, 2021 12:40 pm
Forum: Discrete Mathematics
Topic: Counting constrained squarefree numbers
Replies: 4
Views: 2161

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 ...
by pjt33
Thu Jan 21, 2021 8:26 am
Forum: Discrete Mathematics
Topic: Counting constrained squarefree numbers
Replies: 4
Views: 2161

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 ...
by pjt33
Sat Jan 02, 2021 10:46 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 684
Replies: 16
Views: 7820

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 ...
by pjt33
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: 592

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...
by pjt33
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: 680

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...
by pjt33
Tue Dec 15, 2020 7:02 pm
Forum: Number Theory
Topic: Books in Number Theory
Replies: 1
Views: 1504

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
by pjt33
Thu Dec 10, 2020 8:07 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 737
Replies: 2
Views: 1461

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 ...
by pjt33
Fri Nov 13, 2020 8:41 am
Forum: News, Suggestions, and FAQ
Topic: Website Update (12 Nov 20)
Replies: 8
Views: 2320

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 $$.
by pjt33
Wed Oct 21, 2020 1:01 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 371
Replies: 42
Views: 24595

Re: Problem 371

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.
by pjt33
Tue Oct 20, 2020 8:50 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 371
Replies: 42
Views: 24595

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...
by pjt33
Tue Oct 13, 2020 11:57 am
Forum: News, Suggestions, and FAQ
Topic: Suggestion for new awards
Replies: 3
Views: 1402

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" ...
by pjt33
Thu Oct 08, 2020 7:29 am
Forum: Clarifications on Project Euler Problems
Topic: What kinda math should i know?
Replies: 2
Views: 1440

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...
by pjt33
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: 4629

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...
by pjt33
Tue Sep 29, 2020 8:30 am
Forum: Recreational
Topic: big O notation of PE problems
Replies: 3
Views: 1788

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 ...
by pjt33
Tue Sep 22, 2020 8:27 am
Forum: Recreational
Topic: big O notation of PE problems
Replies: 3
Views: 1788

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...
by pjt33
Sat Sep 19, 2020 11:55 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 710
Replies: 16
Views: 5429

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