Faits:
A.
Par ordonnance du 18 février 2013, le Ministère public de la République et canton de Genève a refusé d'entrer en matière sur la plainte pénale pour escroquerie, faux dans les titres et tentative de contrainte déposée par X._ le 17 septembre 2010.
B.
Par arrêt du 26 mars 2013, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours formé contre cette décision par X._.
C.
Ce dernier interjette un recours en matière pénale auprès du Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, à son annulation et au renvoi de la cause au ministère public pour qu'il poursuive l'instruction, subsidiairement à l'autorité précédente pour nouvelle décision dans le sens des considérants.
Interpellés, l'autorité précédente ne s'est pas déterminée, le ministère public a conclu au rejet du recours. Y._, qui n'a à ce stade pas participé à la procédure cantonale, n'a pu être atteint.

Considérant en droit:
1.
Selon l'art. 81 al. 1 let. a et b ch. 5 LTF, la partie plaignante qui a participé à la procédure de dernière instance cantonale est habilitée à recourir au Tribunal fédéral, si la décision attaquée peut avoir des effets sur le jugement de ses prétentions civiles.
1.1. En règle générale, la partie plaignante doit indiquer quelles conclusions civiles elle entend faire valoir et exposer en quoi la décision attaquée pourrait avoir une incidence négative sur le jugement de celles-ci. Lorsque le recours est dirigé contre une décision de non-entrée en matière ou de classement de l'action pénale, il n'est toutefois pas nécessaire qu'elle ait déjà pris des conclusions civiles. Il suffit qu'elle explique dans son mémoire quelles prétentions civiles elle entend faire valoir contre l'intimé à moins que, compte tenu notamment de la nature de l'infraction alléguée, l'on puisse déduire directement et sans ambiguïté quelles prétentions civiles pourraient être élevées et en quoi la décision attaquée pourrait influencer négativement leur jugement (<ref-ruling> consid. 1.4.1 p. 189; <ref-ruling> consid. 2.4 p. 222).
1.2. En l'occurrence, le recourant invoque que l'intimé, qu'il accuse d'escroquerie, lui aurait vendu un tableau faussement attribué au peintre Claude Monet. Quelques mois plus tard, l'intimé lui aurait remis un certificat d'authenticité concernant le tableau. Soutenant avoir payé cette toile, au moment de la vente, 500'000 USD, le recourant déclare vouloir faire valoir dans le cadre de la procédure pénale des prétentions civiles à hauteur de ce montant au moins. Il a donc qualité pour recourir contre l'arrêt cantonal en ce qui concerne le refus d'entrer en matière sur l'accusation d'escroquerie concernant cette vente. Le recourant ne démontre en revanche pas en quoi il serait lésé par le refus d'entrer en matière sur l'accusation de faux dans les titres, le certificat litigieux lui ayant notamment été remis après qu'il s'est prétendument appauvri du prix de vente, et sur celle de tentative de contrainte. La qualité pour recourir doit par conséquent lui être niée s'agissant de cette partie du fond de la cause.
2.
Au vu des opérations effectuées dans ce dossier, le recourant reproche à l'autorité précédente d'avoir jugé que l'instruction n'avait pas encore été ouverte au sens de l'<ref-law>, de sorte que le ministère public pouvait rendre une ordonnance de non-entrée en matière. Dans ce cadre, le recourant se plaint aussi d'arbitraire dans l'établissement des faits.
2.1. Insuffisamment motivées au regard de l'<ref-law>, les critiques tirées d'un établissement arbitraire des faits sont irrecevables.
2.2. Selon l'<ref-law>, le ministère public ouvre une instruction, lorsqu'il ressort du rapport de police, des dénonciations ou de ses propres constatations, des soupçons suffisants laissant présumer qu'une infraction a été commise (let. a), lorsqu'il ordonne des mesures de contrainte (let. b) ou lorsqu'il est informé par la police conformément à l'<ref-law> (let. c), soit sur les infractions graves et tout autre événement sérieux. Il peut renvoyer à la police, pour complément d'enquête, les rapports et les dénonciations qui n'établissent pas clairement les soupçons retenus (<ref-law>). Le ministère public renonce à ouvrir une instruction lorsqu'il rend immédiatement une ordonnance de non-entrée en matière ou une ordonnance pénale (<ref-law>).
En vertu de l'<ref-law>, le ministère public rend immédiatement une ordonnance de non-entrée en matière s'il ressort de la dénonciation ou du rapport de police que les éléments constitutifs de l'infraction ou les conditions à l'ouverture de l'action pénale ne sont manifestement pas réunis (let. a), qu'il existe des empêchements de procéder (let. b) ou que les conditions mentionnées à l'<ref-law> imposent de renoncer à l'ouverture d'une poursuite pénale (let. c). Le ministère public ne peut donc rendre une ordonnance de non-entrée en matière après avoir ouvert une instruction au sens de l'<ref-law> (Pierre Cornu, Commentaire romand, Code de procédure pénale suisse, 2011, n° 2 ad <ref-law>). Il peut toutefois procéder à certaines vérifications avant de refuser d'entrer en matière. Il peut demander des compléments d'enquête à la police, non seulement lorsqu'il s'agit de compléter un précédent rapport au sens de l'<ref-law>, mais aussi lorsque la dénonciation elle-même apparaît insuffisante. Il ressort également de l'<ref-law> que le ministère public peut procéder à ses propres constatations. Il ne peut en revanche ordonner des mesures de contrainte sans ouvrir une instruction (<ref-law>; arrêt 1B_526/2012 du 24 juin 2013 consid. 2.2).
Lorsqu'il ouvre l'instruction, le ministère public le fait par une ordonnance dans laquelle il désigne le prévenu et l'infraction qui lui est imputée (<ref-law>).
2.3. Le recourant a déposé plainte le 17 septembre 2010. Par courrier du 22 septembre 2010, le Juge d'instruction l'a invité à obtenir d'un institut d'art un avis tranché sur l'authenticité du tableau, ensuite de quoi il requerrait une enquête préliminaire en vue de l'audition de l'intimé. Il a refusé de procéder à une saisie pénale conservatoire. Aucune autre opération n'a été menée en 2010. Le recourant n'invoque pas que l'autorité précédente aurait violé de manière arbitraire le droit cantonal de procédure, applicable jusqu'au 31 décembre 2010, en ne considérant pas qu'une instruction aurait été à ce stade ouverte sous l'égide de ce droit.
Le dossier ne contient pas de décision formelle d'ouverture d'une instruction par le ministère public avec mention du prévenu et des infractions qui lui sont imputées, comme le prévoit l'<ref-law>. Le ministère public n'a ordonné aucune mesure de contrainte. La police a certes pris des renseignements sur l'intimé et la personne indiquée sur le certificat d'authenticité. Elle a également eu des contacts avec un spécialiste de l'art e t procédé à l'audition d'une personne appelée à fournir des renseignements. Il ne s'agit toutefois pas en l'espèce d'opérations dépassant celles de l'investigation policière (<ref-law>). Le 9 février 2012 encore, le procureur en charge du dossier communiquait ainsi avec la police sur la base de l'<ref-law>. Le recourant invoque le courrier du procureur du 12 octobre 2012, qui indiquait que la police est "désormais chargée d'enquêter, y compris de confier l'examen de ce tableau à un expert particulièrement spécialisé en la matière" (recours, p. 9). Les termes utilisés, au vu des seules opérations effectuées mentionnées ci-dessus, ne sauraient impliquer l'ouverture d'une instruction, ce d'autant plus que le procureur n'a finalement pas procédé à la désignation d'un expert au sens de l'<ref-law>. Que le recourant ait eu la possibilité de consulter l'entier de son dossier ne signifie pas non plus qu'une instruction ait été ouverte, encore moins, comme le soutient le recourant, que les preuves essentielles auraient été administrées. Le tableau évoqué par le recourant - et non seulement des photos prétendument de celui-ci - n'a en particulier jamais été retrouvé, encore moins examiné, le lien de causalité entre la vente dudit tableau et le paiement de 500'000 USD apprécié, l'intimé ou le recourant entendu. Le seul écoulement du temps depuis le dépôt de plainte ne donne pas droit à l'ouverture d'une instruction (cf. arrêt 1B_271/2012 du 6 septembre 2012 consid. 2.2). Dans ces circonstances, c'est sans violation de l'<ref-law> que l'autorité précédente a considéré que ce stade n'avait pas été franchi, de sorte qu'une ordonnance de non-entrée en matière pouvait être rendue, moyennant que les autres conditions posées par la loi soient remplies.
3.
Le recourant, après avoir invoqué les conclusions civiles qu'il souhaite prendre contre l'intimé, cite les art. 8 al. 2 let. b et 310 al. 1 let. c CPP et reproche à l'autorité précédente d'avoir considéré qu'il n'avait pas expliqué son intérêt prépondérant à poursuivre la procédure. On comprend qu'il se plaint d'une violation des dispositions susmentionnées.
3.1. En vertu de l'<ref-law>, article auquel renvoie l'art. 310 al. 1 let. c CPP précité, le ministère public renonce à engager une poursuite pénale si aucun intérêt prépondérant de la partie plaignante ne s'y oppose et que la peine qui devrait être prononcée en complément d'une peine entrée en force serait vraisemblablement insignifiante.
Par intérêt de la partie plaignante, on entend notamment celui qu'elle a à ce que ses prétentions civiles, ou encore, dans les cas particulièrement graves, à ce que sa plainte pénale soit traitée (Message relatif à l'unification du droit de la procédure pénale du 21 décembre 2005, FF 2006 1107 ad art. 8). Les prétentions civiles constituent ainsi typiquement un intérêt de la partie plaignante à la poursuite pénale. L'intérêt public au classement l'emporte cependant lorsque, dans un cas « bagatelle » sur le plan pénal, le caractère minime de l'intérêt privé à la poursuite est patent (arrêt 6B_282/2013 du 10 mai 2013 consid. 3.4 et les références citées).
3.2. En l'espèce, le ministère public a considéré que la peine menace pour l'intimé, au vu des infractions visées par la procédure, serait complémentaire à celle de neuf ans prononcée par le Tribunal pénal de Gênes et donc vraisemblablement insignifiante. Invoquant les art. 8 al. 2 let. b et 4 et 310 al. 1 let. c CPP, il a par conséquent décidé de ne pas entrer en matière.
L'autorité précédente a quant à elle considéré que le recourant n'avait pas fait valoir que le ministère public aurait méconnu son éventuel intérêt prépondérant à poursuivre la procédure (arrêt attaqué, p. 3 ch. 3). Le recourant le conteste à juste titre dès lors qu'il s'en est pris en instance cantonale aux conditions de non-entrée en matière, par quoi il a aussi mis en cause la réalisation des conditions de l'<ref-law>.
3.3. Dans sa plainte, le recourant soutient avoir versé à l'intimé, pour un faux tableau, un montant de 500'000 USD qu'il souhaite lui réclamer. Sur la base de telles allégations, l'autorité précédente ne pouvait que constater l'existence d'un intérêt prépondérant du recourant, ce qui excluait une non-entrée en matière fondée sur l'<ref-law>. C'est donc en violation de cette disposition que l'ordonnance de non-entrée en matière a été rendue.
Le recours doit être admis sur ce point et l'affaire renvoyée devant l'autorité précédente. Il lui incombera d'examiner si la procédure doit être continuée ou si un autre motif justifie, avant l'ouverture de l'instruction, de ne pas entrer en matière sur la plainte. Le recourant n'ayant contesté l'ordonnance de non-entrée en matière, de manière recevable, qu'en ce qui concerne l'accusation d'escroquerie liée à la vente du tableau, la procédure ne devra être reprise que sur ce point.
Au vu de ce qui précède, il n'est pas nécessaire d'examiner la violation du droit d'être entendu soulevée par le recourant. Ce dernier invoque une violation du principe de célérité arguant uniquement de la durée de la procédure. Faute de motivation conforme aux exigences posées par les art. 42 al. 2 et 106 al. 2 LTF, son moyen est irrecevable.
4.
Le recours doit être partiellement admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour qu'elle statue dans le sens du considérant qui précède et se prononce à nouveau sur les frais et indemnité. Pour le surplus, le recours doit être rejeté dans la mesure où il est recevable.
Il n'est pas perçu de frais judiciaires (art. 66 al. 1 et 4 LTF). Le canton de Genève versera au recourant une indemnité de dépens pour la procédure devant le Tribunal fédéral (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est partiellement admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision. Pour le surplus, le recours est rejeté dans la mesure où il est recevable.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Genève versera au recourant une indemnité de 2'000 fr. pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève. L'exemplaire de M. Y._ est versé au dossier.
Lausanne, le 18 décembre 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Cherpillod