Search found 17 matches

by castrate
Sat Sep 12, 2020 9:03 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 641
Replies: 6
Views: 3123

Re: Problem 641

I got 69 for n=$10^8$, but the answer for $10^{36}$ was rejected. Can I PM someone for some higher results?
by castrate
Fri Sep 11, 2020 5:00 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?

My algorithm for {1,1,1,...,1} takes roughly O(N). By saying "efficient" here I mean to enumerate numbers of that form without brute force. In other words, an $O(\sqrt[\min(L)]N)$ implementation is efficient enough for me. (Of course, your $O(\sqrt[\max(L)]N)$ approach is much better)
by castrate
Sat Sep 05, 2020 3:59 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?

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.
by castrate
Fri Sep 04, 2020 1:16 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?

Sorry, I don't fully understand your method. Is your $f(k)$, $g(\lfloor \dfrac n k \rfloor )$ equivalent to C(..., k) and C(..., $\lfloor \dfrac n k \rfloor$) as I described above?
by castrate
Fri Sep 04, 2020 4:16 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?

Thanks for your advice, but how may Dirichlet convolution work in this problem? I'm still new to that concept and its applications.
by castrate
Thu Sep 03, 2020 2:13 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

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

For a sorted array of integers L={$a_1,a_2,...,a_k$}(Eg. L=[3,3,2,2,1]), consider numbers n which can be factored in the form: $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, where $p_1, p_2,..., p_k$ are distinct primes . Let E(L, N) be the enumerating function of all numbers n, not exceeding N, which has the ...
by castrate
Mon Aug 31, 2020 12:12 pm
Forum: Number
Topic: Identity involving $\sigma(i·j)$
Replies: 3
Views: 401

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

I found the formula on wolframalpha and solved problem 439 on yesterday evening. Thank you all the same. :D
by castrate
Sat Aug 29, 2020 2:23 am
Forum: Number
Topic: Identity involving $\sigma(i·j)$
Replies: 3
Views: 401

Identity involving $\sigma(i·j)$

As far as I know, there is an identity involving d(i·j), where d(n) denotes the number of divisors of n: $d(i·j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ where [...]=1 if the condition holds, otherwise 0. However, when I was looking for similar identities involving $\sigma(i·j)$ in the form of $\sigma(i·j)...
by castrate
Tue Aug 25, 2020 6:11 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 272
Replies: 15
Views: 10101

Re: Problem 272

I think I'm on the (seemingly)correct way, but the answer was wrong, even not the same with the "correct wrong" answer. Could you please check: Is the smallest number satisfying C(n)=242 <snipped>? And is the smallest number satisfying C(n)=242 and not divisible by 9 <snipped>? Edit: Solved the prob...
by castrate
Fri Aug 21, 2020 1:28 pm
Forum: Number
Topic: Unit cube roots in number theory
Replies: 2
Views: 608

Unit cube roots in number theory

I was trying to solve some particular PE problem these days. It is easy to verify that for any prime power p^k(except 2), there exist two solutions to the equation x^2=1(mod p^k), namely 1 and p^k-1. However, when dealing with the equation x^3=1(mod p^k), the result appeared to differ. For some prim...
by castrate
Mon Aug 03, 2020 9:51 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 688
Replies: 8
Views: 2100

Re: Problem 688

I came across almost the same problem as @TGiordi. I got the correct answer(12656) for S(100) and I was able to compute S(10^16) in reasonable time, but the answer was wrong. So can I PM someone in order to check my answers for higher results such as S(10^8)? Thanks :D
by castrate
Fri Feb 14, 2020 2:56 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 417
Replies: 4
Views: 1182

Re: Problem 417

Solved the problem. :D
Hint removed by moderator
by castrate
Thu Feb 13, 2020 1:04 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 417
Replies: 4
Views: 1182

Re: Problem 417

Sorry for that......So could I PM you or someone else to have a discussion? Thanks :)
by castrate
Wed Feb 12, 2020 9:17 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 417
Replies: 4
Views: 1182

Problem 417

I managed to have written a program which can compute the 10^8 case in acceptable time. However I got a slightly larger result for the test 10^6 case. :?
So could anyone confirm:
n ≤ 100:xxxx results removed by moderator
n ≤ 1000:xxxxx
n ≤ 10000:xxxxxxx
and
n ≤ 100000:xxxxxxxxx?
by castrate
Tue Aug 20, 2019 2:15 pm
Forum: News, Suggestions, and FAQ
Topic: About Statistics-->Countries
Replies: 6
Views: 1407

Re: About Statistics-->Countries

I agree. Thanks a lot.
by castrate
Tue Aug 20, 2019 1:53 pm
Forum: News, Suggestions, and FAQ
Topic: About Statistics-->Countries
Replies: 6
Views: 1407

Re: About Statistics-->Countries

Anyway, anything indicating that these places are independent countries should be avoided.
by castrate
Tue Aug 20, 2019 1:17 pm
Forum: News, Suggestions, and FAQ
Topic: About Statistics-->Countries
Replies: 6
Views: 1407

About Statistics-->Countries

1.jpg 2.jpg 3.jpg Dear Euler: I had solved some dozens of problems before I found this mistake. As you can see, Hong Kong, Macao, and Taiwan are not independent "Countries". As a Chinese user, I cannot accept the way they are categorized, nor do anyone of the other 6000 Chinese programmers. I stron...