## Search found 48 matches

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

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

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

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

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

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

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

- Fri Sep 04, 2020 6:56 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?

No, they're indicator functions $I_L(n) = C(L, n) - C(L, n-1)$.

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

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

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

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

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

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

- 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

Bear in mind that the grouping was made two decades ago, when C++ had diverged much less from C than it has now.

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

- Wed Jun 17, 2020 8:44 pm
- Forum: Recreational
- Topic: Missing Wedding Ring Finger
- Replies:
**18** - Views:
**15798**

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

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

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