Search found 48 matches

by pjt33
Tue Sep 29, 2020 8:30 am
Forum: Recreational
Topic: big O notation of PE problems
Replies: 3
Views: 121

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

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

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

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

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

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

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

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

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

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

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

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

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

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.
by pjt33
Wed Jul 22, 2020 4:42 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 623
Replies: 18
Views: 4544

Re: Problem 623

Also, $\Lambda(n)$ is described as the number of distinct $\alpha$-equivalent lambda-terms that can be written using at most $n$ symbols, but it's actually the number of such symbols which are closed . Thank you for pointing that out, Sardaai. The description has now been updated to ask for closed ...
by pjt33
Wed Jun 17, 2020 8:44 pm
Forum: Recreational
Topic: Missing Wedding Ring Finger
Replies: 18
Views: 15798

Re: Missing Wedding Ring Finger

euler wrote: Sun Jul 17, 2016 1:15 pm The use of the missing finger is a nice angle as that is often ignored in solutions, so there may be some mileage in that. However, keeping a finger on ice for 30 years
is surely not implied at all by ultimatro's answer?
by pjt33
Wed May 27, 2020 7:55 pm
Forum: Number
Topic: Floor sum
Replies: 1
Views: 6173

Re: Floor sum

If there is a solution along similar lines to the one for $\lfloor \sqrt{k} \rfloor$ then it's a polynomial in $n$ and $\lfloor \sqrt{n} \rfloor$. Asymptotically the solution is $\Theta(n^2)$, so there are only 9 coefficients to determine. Pick 9 values of $n$, perform Gaussian elimination to get th...
by pjt33
Fri May 22, 2020 8:35 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 089
Replies: 67
Views: 25517

Re: Problem 089

Nothing wrong with cleverness, but I do think that one of the qualifications for a problem to make it to PE is that it should be a true combination of math and programming, so a problem shouldn't be solvable without a computer doing at least some computation. The compromise position is to include t...
by pjt33
Tue Apr 21, 2020 3:18 pm
Forum: News, Suggestions, and FAQ
Topic: Answer checking API for CI/CD
Replies: 4
Views: 1335

Re: Answer checking API for CI/CD

It would be awesome if it was possible for me to add a script which could check the solutions to the puzzles in the builds which would fail if incorrect. For that use case you don't want an API: you want a local file with test cases. Otherwise your build can randomly fail due either to temporary ne...