Brute force test for Math StackExchange question 612346: http://math.stackexchange.com/questions/612346/

math-se-612346.c

// This program is a quick brute force test of the question described at
// http://math.stackexchange.com/questions/612346/find-all-positive-integers-n-s-t-3n-5n-is-divisible-by-n2-1

// Copyright (C) 2014 Victor Robertson

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

size_t gLower = 1;
size_t gUpper = (0 - 1); // force underflow = size_t max
size_t i;

void sig_handler(int signo)
{
	printf("tested %zu to %zu\n", gLower, i - 1);
	exit(0);
}

int main(int argc, char* argv[]) {

	// all n s.t. 3^n+5^n is divisible by n^2−1

	if (signal(SIGINT, sig_handler) == SIG_ERR) {
		return 1;
	}

	// set args if provided
	if (argc > 1) {
		gLower = atol(argv[1]);
		if (argc > 2) {
			gUpper = atol(argv[2]);
		}
	}
	
	i = gLower;

	mpz_t i_sqr, three_n, five_n, res;

	mpz_init(i_sqr);
	mpz_init(three_n);
	mpz_init(five_n);
	mpz_init(res);

	// start by calculating 3^n and 5^n where n is the first number to test
	mpz_ui_pow_ui(three_n, 3, i);
	mpz_ui_pow_ui(five_n, 5, i);

	// 3 is a known solution, might as well skip straight to 5
	if (gLower < 5) {
		printf("3\n");
		gLower = 5;
	}

	// adjust the lower bound to exclude odds
	if (gLower % 2 == 0) {
		gLower -= 1;
	}

	for(i = gLower; i < gUpper; i += 2) {
		// I think this can be accomplished in a better, possibly more efficient means though I'm not positive.
		mpz_ui_pow_ui(i_sqr, i, 2);
		mpz_sub_ui(i_sqr, i_sqr, 1);

		mpz_add(res, three_n, five_n);

		if (mpz_divisible_p(res, i_sqr)) {
			printf("%zu\n",i);
		}

		// multiple the current 3^n and 5^n by 3 and 5 respectively to acquire 3^(n+1) and 5^(n+1)
		mpz_mul_ui(three_n, three_n, 3);
		mpz_mul_ui(five_n, five_n, 5);
	}

	printf("Done!\n");

	mpz_clear(i_sqr);
	mpz_clear(three_n);
	mpz_clear(five_n);
	mpz_clear(res);
}