A well-known puzzle...

[fivemack]

I wouldn't go as far as to call this elegant, but

* compute 2^a 3^b 5^c 7^d 11^e 13^f 17^g for, say, a=0..6 b=0..4 c=0..3 d=0..3 e=0..2 f=0..2 g=0..2; list the function value and the [abcdefg] in an array F
* sort by function value, so F[0]=1, F[1]=2, ...
* maintain three pointers: 'current' starting at 0, 'plus 17^2' which is the smallest r with F[r]>=289, 'plus 19^2' which is the smallest r with F[r]>=361
* check whether F[x]-F[current] is in the right range and prime for x between 'plus 17^2' and 'plus 19^2'; if so, check whether the [abcdefg] are all not-zero on at least one side
* increment current, then increment the two 'plus' pointers until the inequalities hold again

If you're really clever you can probably use a heap (possibly three heaps) - enumerating smooth numbers in order with a heap is a classic algorithm - but I am not that clever on a Monday afternoon when I'm supposed to be working.

293 = 7293 - 7000
307 = 4675 - 4368
311 = 20111 - 19800
313 = 53625 - 53312
317 = 12285 - 11968
331 = 2431 - 2100
337 = 1724800 - 1724463 (!) 2^7*5^2*7^2*11 - 3^3*13*17^3
353 = 3213 - 2860
359 = 1430 - 1071

389 2926 3315
461 4180 4641
421 4199 4620
367 6783 7150
521 14014 14535
479 24871 25350
503 25432 25935
379 35321 35700
439 43605 44044
509 51205 51714
383 53482 53865
467 65170 65637
443 77077 77520
523 78897 79420
373 88452 88825
409 121856 122265
499 205751 206250
449 230496 230945
401 247000 247401
491 269724 270215
457 371943 372400
463 451737 452200
431 14188744 14189175

but I can't find a representation for 397 yet

[CRGreathouse]

Pari can brute force the solutions up to 389 in about a second:

11 = 2^2 * 3 - 1
13 = 1 + 2^2 * 3
17 = 2 * 3^2 - 1
19 = 1 + 2 * 3^2
23 = 2^3 * 3 - 1
29 = 2 * 3 * 5 - 1
31 = 1 + 2 * 3 * 5
37 = 2^3 * 5 - 3
41 = 3^2 * 5 - 2^2
43 = 3^2 * 5 - 2
47 = 2 + 3^2 * 5
53 = 2^2 * 3 * 5 - 7
59 = 2 * 7 + 3^2 * 5
61 = 2 * 5 * 7 - 3^2
67 = 2 * 5 * 7 - 3
71 = 3 * 5 + 2^3 * 7
73 = 3 + 2 * 5 * 7
79 = 2^2 * 3 * 7 - 5
83 = 2 * 3^2 * 5 - 7
89 = 5 + 2^2 * 3 * 7
97 = 7 + 2 * 3^2 * 5
101 = 3 * 5 * 7 - 2^2
103 = 3 * 5 * 7 - 2
107 = 2 + 3 * 5 * 7
109 = 2^2 + 3 * 5 * 7
113 = 2^3 * 3 * 5 - 7
127 = 2 * 11 + 3 * 5 * 7
131 = 3 * 7 + 2 * 5 * 11
137 = 3 * 5 * 11 - 2^2 * 7
139 = 2 * 7 * 11 - 3 * 5
149 = 2^2 * 11 + 3 * 5 * 7
151 = 3 * 5 * 11 - 2 * 7
157 = 2^2 * 5 * 11 - 3^2 * 7
163 = 2 * 3^2 * 11 - 5 * 7
167 = 5 * 7 + 2^2 * 3 * 11
173 = 3^2 * 7 * 11 - 2^3 * 5 * 13
179 = 3^2 * 11^2 - 2 * 5 * 7 * 13
181 = 2 * 11 * 13 - 3 * 5 * 7
191 = 5 * 7 * 13 - 2^3 * 3 * 11
193 = 7 * 13^2 - 2 * 3^2 * 5 * 11
197 = 2^3 * 13^2 - 3 * 5 * 7 * 11
199 = 2^2 * 7 * 13 - 3 * 5 * 11
211 = 5 * 11 * 13 - 2^3 * 3^2 * 7
223 = 2^3 * 3 * 7 * 11 - 5^3 * 13
227 = 3^2 * 7^3 - 2^2 * 5 * 11 * 13
229 = 5 * 7 * 11 - 2^2 * 3 * 13
233 = 2^3 * 7 * 13 - 3^2 * 5 * 11
239 = 2 * 3 * 5 * 11 - 7 * 13
241 = 2^2 * 3 * 5 * 13 - 7^2 * 11
251 = 7 * 11 * 13 - 2 * 3 * 5^3
257 = 5 * 7 * 13 - 2 * 3^2 * 11
263 = 2 * 5 * 7 * 11 - 3 * 13^2
269 = 3^2 * 7 * 13 - 2 * 5^2 * 11
271 = 2 * 3 * 7 * 13 - 5^2 * 11
277 = 2^2 * 3 * 5 * 7 - 11 * 13
281 = 7 * 11 * 13 - 2^4 * 3^2 * 5
283 = 3^4 * 13 - 2 * 5 * 7 * 11
293 = 3^3 * 5 * 17 - 2 * 7 * 11 * 13
307 = 3^2 * 5^2 * 13 - 2 * 7 * 11 * 17
311 = 7 * 13^2 * 17 - 2^3 * 3^2 * 5^2 * 11
313 = 3^2 * 11^2 * 17 - 2^3 * 5^2 * 7 * 13
317 = 2^2 * 5^2 * 7 * 17 - 3^4 * 11 * 13
331 = 11 * 13 * 17 - 2^2 * 3 * 5^2 * 7
337 = 2^7 * 5^2 * 7^2 * 11 - 3^3 * 13 * 17^3
347 = 3^2 * 7^2 * 17 - 2 * 5^2 * 11 * 13
349 = 2 * 5 * 7 * 13 - 3 * 11 * 17
353 = 3^3 * 7 * 17 - 2^2 * 5 * 11 * 13
359 = 2 * 5 * 11 * 13 - 3^2 * 7 * 17
367 = 2 * 5^2 * 11 * 13 - 3 * 7 * 17 * 19
373 = 5^2 * 11 * 17 * 19 - 2^2 * 3^5 * 7 * 13
379 = 2^2 * 3 * 5^2 * 7 * 17 - 11 * 13^2 * 19
383 = 3^4 * 5 * 7 * 19 - 2 * 11^2 * 13 * 17
389 = 3 * 5 * 13 * 17 - 2 * 7 * 11 * 19

397 also gives me trouble; it has no small solutions. 419 isn't much better.

[mart_r]

Originally Posted by CRGreathouse

Pari can brute force the solutions up to 389 in about a second

:surprised
I feel outdated.

[CRGreathouse]

Originally Posted by mart_r

I feel outdated.

Don't. The algorithm I used won't scale -- for numbers like 397 it probably wouldn't ever find the solution.

Here's the core of the program:

find(p)={
	local(pr=primorial(sqrtint(p)));
	for(a=1,9e99,
		if (check(a),
			if (check(abs(p-a)) && check2(a, abs(p-a)), return(a));
			if (check(p+a) && check2(a, p+a), return(a));
		)
	)
};
\\ check(n): Is n p-smooth for p# = pr? Uses the local variable pr.
check(n)={
	my(g);
	while((g=gcd(n, pr)) > 1,
		n \= g
	);
	n == 1
};
\\ check2(a, b): Do a and b together use all the prime factors in p# = pr? Uses the local variable pr.
check2(a, b)={
	gcd(a*b, pr) == pr
};

Not included: primorial (obvious), nice (puts results into output format), fnice (displays a factored number). [2.4.2 users: note that this uses local and *not* my.]

[10metreh]

Originally Posted by CRGreathouse

Don't. The algorithm I used won't scale -- for numbers like 397 it probably wouldn't ever find the solution.

Here's the core of the program:

find(p)={
    local(pr=primorial(sqrtint(p)));
    for(a=1,9e99,
        if (check(a),
            if (check(abs(p-a)) && check2(a, abs(p-a)), return(a));
            if (check(p+a) && check2(a, p+a), return(a));
        )
    )
};
\\ check(n): Is n p-smooth for p# = pr? Uses the local variable pr.
check(n)={
    my(g);
    while((g=gcd(n, pr)) > 1,
        n \= g
    );
    n == 1
};
\\ check2(a, b): Do a and b together use all the prime factors in p# = pr? Uses the local variable pr.
check2(a, b)={
    gcd(a*b, pr) == pr
};

Not included: primorial (obvious), nice (puts results into output format), fnice (displays a factored number). [2.4.2 users: note that this uses local and *not* my.]

You think you know everything Pari can do, and then you always find something new!

[CRGreathouse]

Originally Posted by 10metreh

You think you know everything Pari can do, and then you always find something new!

Out of curiosity... what was new? My vs. local? I thought my script was pretty boneheaded, myself. (I did make some minor improvements after posting, like using valuation(n, 2) in check(n) to quickly remove trailing binary 0s, but those weren't significant enough to post.)

[10metreh]

Originally Posted by CRGreathouse

Out of curiosity... what was new? My vs. local? I thought my script was pretty boneheaded, myself. (I did make some minor improvements after posting, like using valuation(n, 2) in check(n) to quickly remove trailing binary 0s, but those weren't significant enough to post.)

Just a comment... about other cases.

[CRGreathouse]

Originally Posted by fivemack

but I can't find a representation for 397 yet

I wrote another program, still not very good but more scalable than the other. I checked up to a googol and didn't find anything for 397.

A truly naive system checks n candidates up to n. A scalable system generates smooth numbers and checks only those; there are

such numbers. (The constant factor here is about 330 with a natural log.)

But the complexity can be further reduced (at a cost of increasing the constant factor, in this case by a factor of 154 to about 51,000) to

by checking {2, 3}-smooth, {2, 5}-, ..., {11, 13, 17, 19}-smooth numbers only. (My program checks for {3, 5, 7, 11, 13, 17, 19}-smooth numbers only, which reduces the exponent by 1 with no cost to the constant factor.)

This is because at least one of the addends has <= floor(pi(sqrt(397))) = 4 prime factors.

A proper implementation of this system should be able to reach 10^2000, making many unjustified assumptions about the time needed to generate and check each number.

[m_f_h]

Essentially your find() is the same as the highly unoptimized (in favour of utmost simplicity)

M(n)={ my(p=vector(primepi(sqrtint(n)),i,prime(i))~); for( m=1,1e9,
(factor(m*(n+m))[,1]==p | factor(m*abs(m-n))[,1]==p) & return(m))}

(where one could (to make it faster than your find() ;-) add
"m>n & vecmax(factor(m)[,1])>p[#p] & next;")

and it would correspond to the sequence
(I'd add the information about the relative sign)

M(n) = Smallest integer m, in absolute value, such that |m(prime(n)+m)| has as prime factors exactly all primes < sqrt(prime(n)).

Indeed, gcd(m,p+-m)=1 for any prime p not dividing m, thus the factors in m cannot be in p+-m.
Since we want that the union of prime factors of m and p+-m are all primes < sqrt(p), it is equivalent to ask this for their product.

I think it would indeed be way more efficient to create a list of sqrt(n)-smooth numbers.

[m_f_h]

Continuation of the puzzle : prove or disprove that A(n) >= 0 for all sufficiently large integers, where

A(n) = Smallest integer m, in absolute value, such that |m(n+m)| has as prime factors exactly all primes <= sqrt(n); 0 if no such m exists.

(In case of a tie (m and -m would do), chose A(n)=|m|.)

Sequence starts (at n=4):
-2, -1, 2, 1, -4, 3, 2, 1, 6, -1, -2, 3, 2, 1, 6, -1, -2, 3, 2, 1, -6, 5, 4, 3, 2, 1, 60, -1, -2, -3, -4, -5, -6, 3, -8, 6, -10, 4, -12, 2, 6, 15, -6, -2, 12, 21, 70, -21, -10, 7, 30, 15, 70, -15, 12, -14, 150, 9, -20, 42, 6, -30, 60, 3, 30, 15, 140, -15, -30, -3, 10, 30, -6, 28, 42, 5, 60, -21, -12, 7, 126, -15, -30, 18, -18, -5, 120, 14, 28, 12, -10, 10, 30, -7, 42, 6, -30, 4, -42, 2, -14, 210, 14, -2, 42, -4, 30, -6, -42, 7, -30, -10, 10, -12, -28, -14, 90, 110, 88, 42, 30, 315, 924, -22, 70, 165, 420, -21, 330, 77, 196, 495, -66, 28, 462, 15, 630, 90, 110, 165, 66, 240, 154, 315, 132, -44, 840, 14, -42, 210, 770, 55, 264, 63, 150, 105, 330, 70, 168, 35, 396, 990, 44, -35, 462, 546, 1260, 819, 2600, 520, 1386, 1365, 1540, 1188, 37730, 910, 5280, 105, 8008, 1287, 726, 585, 2310, 1430, 462, 2541, 4290, 264, 858, 990, 1456, 4095, 3080, 1155, 9240, 165, 7150, 429, 260, 1617, 1980, 455, 1950, 2145, 1430, 715, 13650, 504, 880, 7392, 2646, 1540, 330, 693, 4732, 210, 6930, 780, 14520, 1625, 546, 2310, 390, 2860, 630, 156, 2080, 5775, 1848, 495,6006, 2625, 154, 1050, 2310, 91, 2730, 539, 5148, 3432, 770, 910, 924, 1755, 2002, 1155, 660, 750, 4368, 462, 1176, 1890, 1694, 198, 3900, 1001, 4290, 1650, 728, 507, 2310, 1100, 2464, 195, 572, 550, 7920, 275, 2640, 2730, 650, 1155, 3234, 143, 910, 546, 8190, 720, 2028, 770, 990, 1365, 4004, 1078, 1560, 2805, 44590, 3570, 13260, 2002, 64680, 60480, 7140, 28875, 16940, 2431, 6630, 10710, 63580, 78897, 16016, 5610, 14280, 2618, 219912, 4641, 22440, 19800, 174720, 18200, 1870, 30030, ...