Search found 53 matches

by pjt33
Wed Oct 21, 2020 1:01 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 371
Replies: 42
Views: 18814

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: 18814

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: 288

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

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 what expectation is...
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: 3471

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: 675

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: 675

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: 13
Views: 2474

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

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.
by pjt33
Thu Sep 10, 2020 2:56 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 004
Replies: 85
Views: 21740

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

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

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". Lo...
by pjt33
Fri Sep 04, 2020 8:08 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

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)$.
by pjt33
Thu Sep 03, 2020 11:12 pm
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

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...
by pjt33
Wed Sep 02, 2020 8:10 am
Forum: Number
Topic: Identity involving $\sigma(i·j)$
Replies: 3
Views: 631

Re: Identity involving $\sigma(i·j)$

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...
by pjt33
Fri Aug 28, 2020 11:57 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 431
Replies: 10
Views: 4221

Re: Problem 431

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 ...
by pjt33
Sat Aug 22, 2020 1:06 am
Forum: Number
Topic: Unit cube roots in number theory
Replies: 2
Views: 849

Re: Unit cube roots in number theory

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...
by pjt33
Thu Aug 13, 2020 5:28 pm
Forum: News, Suggestions, and FAQ
Topic: Website Maintenance 30 July 2020
Replies: 35
Views: 4532

Re: Website Maintenance 30 July 2020

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.
by pjt33
Tue Aug 04, 2020 11:02 am
Forum: Programming languages
Topic: the Spartan way of C
Replies: 5
Views: 1076

Re: the Spartan way of C

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.