tôi đã tìm thấy chuỗi này tương tự như chuỗi Marcin Ciura của:
1, 4, 9, 23, 57, 138, 326, 749, 1695, 3785, 8359, 18298, 39744, etc.
Ví dụ, chuỗi Ciura là:
1, 4, 10, 23, 57, 132, 301, 701, 1750
Đây là một trung bình của số nguyên tố. Python mã để tìm nghĩa của số nguyên tố là ở đây:
import numpy as np
def isprime(n):
''' Check if integer n is a prime '''
n = abs(int(n)) # n is a positive integer
if n < 2: # 0 and 1 are not primes
return False
if n == 2: # 2 is the only even prime number
return True
if not n & 1: # all other even numbers are not primes
return False
# Range starts with 3 and only needs to go up the square root
# of n for all odd numbers
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return True
# To apply a function to a numpy array, one have to vectorize the function
vectorized_isprime = np.vectorize(isprime)
a = np.arange(10000000)
primes = a[vectorized_isprime(a)]
#print(primes)
for i in range(2,20):
print(primes[0:2**i].mean())
Đầu ra là:
4.25
9.625
23.8125
57.84375
138.953125
326.1015625
749.04296875
1695.60742188
3785.09082031
8359.52587891
18298.4733887
39744.887085
85764.6216431
184011.130096
392925.738174
835387.635033
1769455.40302
3735498.24225
Khoảng cách trong chuỗi đang dần giảm từ 2,5 đến 2. Có lẽ sự kết hợp này có thể cải thiện Shellsort trong tương lai.
Nguồn
2017-09-08 14:56:13
Ai đó đã đào ra trình tự của tôi :-) Tôi đã triển khai thuật toán sắp xếp trên tập dữ liệu rất hạn chế về kích thước - khoảng 10 đến 50 và tôi thấy shellsort là trình duyệt nhanh nhất trong phạm vi này. Tôi tìm kiếm kỹ lưỡng trình tự tốt nhất - và tìm thấy chủ yếu là Knuth, Sedgewicks, vv, mà chủ yếu dựa trên voodoo và kumba wamba. Marcin Ciuara có vẻ là một trong số ít những người thực sự đã làm một số tiêu chuẩn và có cái gì đó tốt hơn so với trình tự dựa trên một công thức ma thuật, và đây là lý do chính tôi đăng nó trên OEIS. Nhưng tôi không có câu trả lời cho bạn. – hirschhornsalz
Trình tự phải được giảm nghiêm ngặt và yếu tố cuối cùng của nó luôn luôn là 1. Nếu khoảng cách là 1, nó có nghĩa là sắp xếp cổ điển. Vì vậy, chuỗi của Ciura chính xác là [701, 301, 132, 57, 23, 10, 4, 1]. Tôi đã thực hiện một số thử nghiệm và trình tự ban đầu của Shell hoạt động tốt hơn cho tôi. – Jabba
Liên kết bạn đã cung cấp bị hỏng. _ "Tăng trưởng tốt nhất cho trường hợp trung bình của Shellsort" _: [abstract] (http://www.springerlink.com/content/2akgu9pvc6jl239g/) và [full paper] (http://sun.aei.polsl.pl/ ~ mciura/publikacje/shellsort.pdf) – user46874