Lời khuyên cho Dự án Euler Vấn đề # 78

Question

Đây là vấn đề được đề cập: Problem #78

Điều này khiến tôi phát điên. Tôi đã làm việc này trong vài giờ và tôi đã có thể làm giảm sự phức tạp của việc tìm kiếm số cách để thu tiền n tiền xu đến O(n/2), nhưng ngay cả với những cải tiến đó và bắt đầu từ số n mà p(n) gần một triệu, tôi vẫn không thể đạt được câu trả lời trong chưa đầy một phút. Không thực sự.

Có bất kỳ gợi ý nào có thể giúp tôi với điều này không?

Hãy nhớ rằng tôi không muốn một giải pháp đầy đủ và không nên có bất kỳ giải pháp chức năng nào được đăng ở đây, để không làm hỏng vấn đề cho người khác. Đây là lý do tại sao tôi chưa bao gồm bất kỳ mã nào.

Answer 1

Wikipedia có thể giúp bạn tại đây. Tôi cho rằng giải pháp mà bạn đã có là đệ quy chẳng hạn như giải pháp trong phần "hàm trung gian". Điều này có thể được sử dụng để tìm giải pháp cho vấn đề Euler, nhưng không nhanh.

Cách tốt hơn là sử dụng đệ quy dựa trên số pentagonal number theorem trong phần tiếp theo. Bằng chứng của định lý này không thẳng về phía trước, vì vậy tôi không nghĩ rằng các tác giả của vấn đề mong đợi rằng bạn đưa ra định lý của chính mình. Thay vào đó nó là một trong những vấn đề, nơi họ mong đợi một số tìm kiếm văn học.

Answer 2

đây một số gợi ý:

1. chia hết bởi một triệu không phải là điều tương tự như chỉ là lớn hơn một triệu người. 1 triệu = 1.000.000 = 10^6 = 2^6 * 5^6.

2. Vì vậy, câu hỏi đặt ra là tìm giá trị n thấp nhất sao cho các thừa số của p (n) chứa 6 và 6 của 5.

Answer 3

Bạn đã gặp sự cố 31 hoặc 76 chưa? Chúng tạo thành một bộ tốt đẹp, đó là sự tổng quát hóa cùng một vấn đề cơ sở mỗi lần. Làm các câu hỏi dễ dàng hơn có thể cung cấp cho bạn thông tin chi tiết về giải pháp cho 78.

Answer 4

Vấn đề này thực sự yêu cầu tìm cụm từ đầu tiên trong chuỗi phân hoạch số nguyên có thể chia hết cho 1.000.000.

Phân vùng của số nguyên, n, là một cách mô tả số lượng tổng các số nguyên dương, ≤ n, có thể được cộng lại với nhau bằng n, bất kể thứ tự. Hàm p (n) được sử dụng để biểu thị số lượng phân vùng cho n. Dưới đây chúng tôi hiển thị 5 "tiền xu" của chúng tôi như là phụ lục để đánh giá 7 phân vùng, đó là p (5) = 7.

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

Chúng tôi sử dụng chức năng tạo để tạo chuỗi cho đến khi chúng tôi tìm thấy yêu cầu n. Chức năng tạo ra đòi hỏi tối đa 500 cái gọi là số ngũ giác tổng quát, được cho bởi n (3n - 1)/2 với 0, ± 1, ± 2, ± 3 ..., số đầu tiên trong số đó là 0, 1, 2, 5, 7, 12, 15, 22, 26, 35,… (Sloane's A001318).

Chúng tôi có chức năng tạo ra sau đó sử dụng số ngũ giác của chúng tôi như số mũ:

1 - q - q^2 + q^5 + q^7 - q^12 - q^15 + q^22 + q^26 + ...

blog của tôi tại blog.dreamshire.com có ​​chương trình perl giải quyết vấn đề này sau chưa đầy 10 giây.